Almost linear upper bounds on the length of general Davenport-Schinzel sequences. (English) Zbl 0636.05004

(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 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. \]
Reviewer: M.Sharir


05A10 Factorials, binomial coefficients, combinatorial functions


Zbl 0636.05003
Full Text: DOI


[1] W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen,Math. Ann.,99 (1928), 118–133. · JFM 54.0056.06
[2] M. Atallah, Dynamic Computational Geometry,Proc. 24 th Symp. on Foundations of Computer Science, (1983), 92–99.
[3] H. Davenport, A Combinatorial Problem Connected with Differential Equations, II.Acta Arithmetica,17 (1971), 363–372. · Zbl 0216.30204
[4] H. Davenport andA. Schinzel, A Combinatorial Problem Connected with Differential Equations,Amer. J. Math.,87 (1965), 684–694. · Zbl 0132.00601
[5] S. Hart andM. Sharir, Nonlinearity of Davenport–Schinzel Sequences and of Generalized Path Compression Schemes,Combinatorica,6 (1986), 151–177. · Zbl 0636.05003
[6] D. P. Roselle andR. G. Stanton, Some Properties of Davenport–Schinzel Sequences,Acta Arithmetica,17 (1971), 355–362. · Zbl 0215.33203
[7] E. Szemerédi, On a Problem by Davenport and Schinzel,Acta Arithmetica,25 (1974), 213–224.
[8] R. E. Tarjan, Efficiency of a Good but not Linear Set-union Algorithm,J. Assoc. Computing Machinery,22 (1975), 215–225. · Zbl 0307.68029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.