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; Zbl 0636.05003), see the preceding review] 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. Szemerédi [Acta Arith. 25, 213–224 (1974; Zbl 0291.05003)].
The results of this paper have later been slightly improved by P. K. Agarwal, the author and P. Shor [J. Comb. Theory, Ser. A 52, No. 2, 228–274 (1989; Zbl 0697.05003)], who have shown that \[ \lambda_{2s}(n) = O(n\cdot 2^{O(\alpha(n)^{s-1})}),\quad\text{for } s\geq 2, \] \[ \lambda_{2s+1}(n) = O(n\cdot \alpha(n)^{O(\alpha(n)^{s-1})}),\quad \text{for } 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\text{for } s\geq 2. \]
Reviewer: M. Sharir


05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
11B83 Special sequences and polynomials
Full Text: DOI


[1] W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen,Math. Ann.,99 (1928), 118–133. · doi:10.1007/BF01459088
[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 · doi:10.2307/2373068
[5] S. Hart andM. Sharir, Nonlinearity of Davenport–Schinzel Sequences and of Generalized Path Compression Schemes,Combinatorica,6 (1986), 151–177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.