Sharp Bounds on Davenport-Schinzel Sequences of Every Order

摘要

One of the oldest unresolved problems in extremal combinatorics is to determine the maximum length of Davenport-Schinzel sequences, where an orders DS sequence is defined to be one over an n-letter alphabet that avoids alternating subsequences of the form a…b… a…b…with length s + 2. These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since become an indispensable tool in computational geometry and the analysis of discrete geometric structures. Let λ_s(n) be the extremal function for such sequences. What is λ_s asymptotically? This question has been answered satisfactorily (by Hart and Sharir, Agarwal, Sharir, and Shor, and Nivasch) when s is even or s ≤ 3. However, since the work of Agarwal, Sharir, and Shor in the 1980s there has been a persistent gap in our understanding of the odd orders, a gap that is just as much qualitative as quantitative. In this paper we establish the following bounds on λ_s(n) for every order s. λ_s(n) ={n s=1 2n-1 s=2 2nα(n)+O(n) s=3 direct-(n2~(α(n))) s=4 direct(nα(n)2~(α(n))) s=5 n2(1+o(1))α~t(n)/t! s≥6 t=[(s-2)/2] These results refute a conjecture of Alon, Kaplan, Nivasch, Sharir, and Smorodinsky and run counter to common sense. When λ_s is odd, λ_s behaves essentially like λ_(s-1).