### Sharp Bounds on Davenport-Schinzel Sequences of Every OrderSharp Bounds on Davenport-Schinzel Sequences of Every Order

Access Restriction
Subscribed

 Author Pettie, Seth Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Combinatorics ♦ Forbidden patterns ♦ Sequences Abstract One of the longest-standing open problems in computational geometry is bounding the complexity of the lower envelope of $\textit{n}$ univariate functions, each pair of which crosses at most $\textit{s}$ times, for some fixed $\textit{s}.$ This problem is known to be equivalent to bounding the length of an $order-\textit{s}$ Davenport-Schinzel sequence, namely, a sequence over an $\textit{n}-letter$ alphabet that avoids alternating subsequences of the form $\textit{a}$ &cdots; $\textit{b}$ &cdots; $\textit{a}$ &cdots; $\textit{b}$ &cdots; with length $\textit{s}+2.$ These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bound the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements. Let $Δ_{s}(n)$ be the maximum length of an $order-\textit{s}$ DS sequence over $\textit{n}$ letters. What is $Δ_{s}$ asymptotically? This question has been answered satisfactorily [Hart and Sharir 1986; Agarwal et al. 1989; Klazar 1999; Nivasch 2010], when $\textit{s}$ is even or $\textit{s}≤$ 3. However, since the work of Agarwal et al. in the mid-1980s, there has been a persistent gap in our understanding of the odd orders. In this work, we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order $\textit{s}.$ Our results reveal that, contrary to one's intuition, $Δ_{s}(n)$ behaves essentially like $Δ_{s-1}(n)$ when $\textit{s}$ is odd. This refutes conjectures by Alon et al. [2008] and Nivasch [2010]. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-11-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 5 Page Count 40 Starting Page 1 Ending Page 40

#### Open content in new tab

Source: ACM Digital Library