Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations

ABSTRACT

We present several new results regarding λ_s(n), the maximum length of a Davenport--Schinzel sequence of order s on n distinct symbols.

First, we prove that

[EQUATION]

where t = [(s - 2)/2], and α(n) denotes the inverse Ackermann function. The previous upper bounds, by Agarwal, Sharir, and Shor (1989), had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al.

More importantly, we also present a new technique for deriving upper bounds for λ_s(n). This new technique is based on some recurrences very similar to those used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of λ₃(n) ≤ 2nα(n)+O(n)√α(n) (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport--Schinzel sequences considered by Adamec, Klazar, and Valtr (1992).

Regarding lower bounds, we show that λ₃(n) ≥ 2nα(n) - O (n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of λ_s(n) ≥ n·2^{(1/t!)α(n)t - O (α(n)t-1)} for s ≥ 4 even.

REFERENCES

• 1: Radek Adamec , Martin Klazar , Pavel Valtr, Generalized Davenport-Schinzel sequences with linear upper bound, Discrete Mathematics, v.108 n.1-3, p.219-229, Oct. 28, 1992 [doi>10.1016/0012-365X(92)90677-8]
• 2: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• 3: Noga Alon , Ehud Friedgut, On the number of permutations avoiding a given pattern, Journal of Combinatorial Theory Series A, v.89 n.1, p.133-140, Jan. 2000 [doi>10.1006/jcta.1999.3002]
• 4: Noga Alon , Haim Kaplan , Gabriel Nivasch , Micha Sharir , Shakhar Smorodinsky, Weak ε-nets and interval chains, Journal of the ACM (JACM), v.55 n.6, p.1-32, December 2008 [doi>10.1145/1455248.1455252]
• 5: H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, American J. Math., 87:684--694, 1965.
• 6: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 7: M. Klazar, A general upper bound in extremal theory of sequences, Comment. Math. Univ. Carol., 33:737--746, 1992.
• 8: M. Klazar, On the maximum lengths of Davenport--Schinzel sequences, in R. Graham et al., editors, Contemporary Trends in Discrete Mathematics (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 49), pp. 169--178, Amer. Math. Soc., Providence, RI, 1999.
• 9: M. Klazar, Generalized Davenport--Schinzel sequences: Results, problems, and applications, Integers, 2:A11, 39 pp. (electronic), 2002.
• 10: Péter Komjáth, A simplified construction of nonlinear Davenport—Schinzel sequences, Journal of Combinatorial Theory Series A, v.49 n.2, p.262-267, Nov. 1988 [doi>10.1016/0097-3165(88)90055-6]
• 11: Adam Marcus , Gábor Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, Journal of Combinatorial Theory Series A, v.107 n.1, p.153-160, July 2004 [doi>10.1016/j.jcta.2004.04.002]
• 12: Seth Pettie, Splay trees, Davenport-Schinzel sequences, and the deque conjecture, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1115-1124, January 20-22, 2008, San Francisco, California
• 13: R. Seidel, Understanding the inverse Ackermann function, PDF presentation. Available at http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf.
• 14: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 15: R. Sundar, On the deque conjecture for the splay algorithm, Combinatorica, 12:95--124, 1992.
• 16: P. Valtr, Generalizations of Davenport--Schinzel sequences, in R. Graham et al., editors, Contemporary Trends in Discrete Mathematics (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 49), pp. 349--389, Amer. Math. Soc., Providence, RI, 1999.
• 17: Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems