Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizationsImproved bounds and new techniques for Davenport--Schinzel sequences and their generalizations

Access Restriction
Subscribed

 Author Nivasch, Gabriel Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Davenport--Schinzel sequence ♦ Inverse Ackermann function ♦ Lower envelope Abstract We present several new results regarding $λ_{s}(n),$ the maximum length of a Davenport--Schinzel sequence of order $\textit{s}$ on $\textit{n}$ distinct symbols. First, we prove that $λ_{s}(n)$ ≤ $\textit{n}$ ṡ $2^{(1/t&excel;)α(n)^{t}$ + $O(α(n)^{t™1})}$ for $\textit{s}$ ≥ 4 even, and $λ_{s}(n)$ ≤ $\textit{n}$ ṡ $2^{(1/t&excel;)α(n)^{t}$ $log_{2}$ $α(\textit{n})$ + $O(α(n)^{t})}$ for $\textit{s}≥$ 3 odd, where $\textit{t}$ = $⌊(\textit{s}™2)/2⌋,$ and $α(\textit{n})$ denotes the inverse Ackermann function. The previous upper bounds, by Agarwal et al. [1989], had a leading coefficient of 1 instead of $1/\textit{t}&excel;$ in the exponent. The bounds for even $\textit{s}$ are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al. More importantly, we also present a new technique for deriving upper bounds for $λ_{s}(n).$ This new technique is very similar to the one we applied to the problem of stabbing interval chains [Alon et al. 2008]. With this new technique we: (1) re-derive the upper bound of $λ_{3}(n)$ ≤ $2\textit{n}$ $α(\textit{n})$ + $\textit{O}(\textit{n}$ $&sqrt;α(\textit{n}))$ (first shown by Klazar [1999]); (2) re-derive our own new upper bounds for general $\textit{s}$ and (3) obtain improved upper bounds for the generalized Davenport--Schinzel sequences considered by Adamec et al. [1992]. Regarding lower bounds, we show that $λ_{3}(n)$ ≥ $2\textit{n}$ $α(\textit{n})$ ™ $\textit{O}(\textit{n})$ (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal et al. [1989] that achieves the known lower bounds of $λ_{s}(n)$ ≥ $\textit{n}$ ṡ $2(1/\textit{t}&excel;)$ $α(n)^{t}$ ™ $O(α(n)^{t™1})}$ for $\textit{s}$ ≥ 4 even. 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 2010-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 3 Page Count 44 Starting Page 1 Ending Page 44

Open content in new tab

Source: ACM Digital Library