← 研踪 PaperTrailarXiv:2611.26297 · v1
Exact guarantees and faster algorithms for $k$-rollercoasters
首次提交 2026-11-19 23:51
版本更新 2026-11-19 23:51
雷达观测 2026-11-20 14:52
摘要
For , a -rollercoaster is a sequence of distinct values whose maximal increasing and decreasing runs all have length at least . We discover the maximum guaranteed length of -rollercoasters appearing as subsequences of -point permutations. In particular, letting , we prove that for , for and otherwise. We prove that the guarantees are tight by constructing an -point permutation whose longest -rollercoaster has exactly points. Our proof extends Seidenberg's argument [Journal of the London Mathematical Society, 1959] for proving the Erdős--Szekeres theorem by representing points in a subsequence with respect to the lengths of longest monotonic (increasing and decreasing) subsequences that reach each point. The combinatorial proof yields a deterministic comparison-based algorithm that finds a rollercoaster of length at least in time and space for . Independently, we give an -time, -space algorithm for a longest -rollercoaster, improving the previous bound. We use the dynamic program of Gawrychowski et al. [STACS 2019, Algorithmica 2022], and process its weighted predecessor queries through monotone subsequences with finger-search trees. Both algorithms return such subsequences.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 23:51 · 最新观测版本
Exact guarantees and faster algorithms for $k$-rollercoasters
For , a -rollercoaster is a sequence of distinct values whose maximal increasing and decreasing runs all have length at least . We discover the maximum guaranteed length of -rollercoasters appearing as subsequences of -point permutations. In particular, letting , we prove that for , for and otherwise. We prove that the guarantees are tight by constructing an -point permutation whose longest -rollercoaster has exactly points. Our proof extends Seidenberg's argument [Journal of the London Mathematical Society, 1959] for proving the Erdős--Szekeres theorem by representing points in a subsequence with respect to the lengths of longest monotonic (increasing and decreasing) subsequences that reach each point. The combinatorial proof yields a deterministic comparison-based algorithm that finds a rollercoaster of length at least in time and space for . Independently, we give an -time, -space algorithm for a longest -rollercoaster, improving the previous bound. We use the dynamic program of Gawrychowski et al. [STACS 2019, Algorithmica 2022], and process its weighted predecessor queries through monotone subsequences with finger-search trees. Both algorithms return such subsequences.
查看此版本解读 →查看此版本原文 ↗