Improved lower bounds on the length of Davenport-Schinzel sequences. (English) Zbl 0672.05015

For the longest length of general Davenport-Schinzel sequences, i.e. sequences of n letters with no immediate repetitions and no subsequence of type a..b..a..b..a.. of length \(s+2\), the estimate \(\Omega (n\alpha^ s(n))\) is established, where \(\alpha\) (n) is the inverse of the Ackermann function. This improves earlier bounds. The proof uses generalized path compression schemes.
Reviewer: P.Komjáth


05A99 Enumerative combinatorics
05C35 Extremal problems in graph theory
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] M.Atallah, Dynamic computational geometry,Proc. 24th Symp. on Foundations of Computer Science, (1983), 92–99.
[2] A.Baltsan and M.Sharir, On shortest paths between two convex polyhedra,Tech. Rept. 180, Comp. Science Dept., Courant Institute, Sept. 1985. · Zbl 0652.68043
[3] 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
[4] H. Davenport, A combinatorial problem connected with differential equations, II.Acta Arithmetica,17 (1971), 363–372. · Zbl 0216.30204
[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. Leven andM. Sharir, On the number of critical free contacts of a convex polygonal object moving in 2-D polygonal space,Discrete Comput. Geom.,2 (1987), 255–270. · Zbl 0616.52009 · doi:10.1007/BF02187883
[7] C. O’Dúnlaing, M. Sharir andC. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram,Algorithmica,2 (1987), 27–59. · Zbl 0631.68042 · doi:10.1007/BF01840348
[8] M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences,Combinatorica,7 (1987), 131–143. · Zbl 0636.05004 · doi:10.1007/BF02579209
[9] E. Szemerédi, On a problem by Davenport and Schinzel,Acta Arithmetica,25 (1974), 213–224.
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.