Access Restriction

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

   Open content in new tab
Source: ACM Digital Library