Almost linear upper bounds on the length of general Davenport-Schinzel sequences (Q1097885): Difference between revisions

(n,s)-Davenport-Schinzel sequences are sequences that are composed of n symbols, and are such that (i) no two adjacent elements are equal, and (ii) there does not exist a (not necessarily contiguous) alternating subsequence of length \(s+2\) of the form a...b...a...b... for any two distinct symbols a and b. Davenport-Schinzel sequences arise in the computation and analysis of the lower or upper envelope of a set of functions, and are thus a powerful and versatile tool for a variety of problems in combinatorial and computational geometry. This paper establishes almost linear upper bounds on the maximum length \(\lambda_ s(n)\) of (n,s) Davenport-Schinzel sequences. These bounds are of the form \(O(n\alpha (n)^{O(\alpha (n)^{s-3})})\), and they generalize and extend the tight bound \(\Theta\) (n\(\alpha\) (n)) obtained by \textit{S. Hart} and the author [ibid. 6, 151-177 (1986; see above, Zbl 0636.05003)] for the special case \(s=3\) (\(\alpha\) (n) is the extremely slowly growing functional inverse of Ackermann's function), and also improve the upper bound O(n log *n) due to E. Szemeredi (1974). The results of this paper have later been slightly improved by Agarwal, Sharir and Shor (1988), who have shown that \[ \lambda_{2s}(n)=O(n\cdot 2^{O(\alpha (n)^{s-1})}),\quad for\quad s\geq 2,\quad \lambda_{2s+1}(n)=O(n\cdot \alpha (n)^{O(\alpha (n)^{s-1})}),\quad for\quad s\geq 2. \] Moreover, these bounds are almost tight for even s, because \[ \lambda_{2s}(n)=\Omega (n\cdot 2^{\Omega (\alpha (n)^{s- 1})}),\quad for\quad s\geq 2. \]