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

Abstract

Let lambda_s(n) denote the maximum length of a Davenport-Schinzel sequence of order s on n symbols. For s=3 it is known that lambda_3(n) = Theta(n alpha(n)) (Hart and Sharir, 1986). For general s>=4 there are almost-tight upper and lower bounds, both of the form n * 2^poly(alpha(n)) (Agarwal, Sharir, and Shor, 1989). Our first result is an improvement of the upper-bound technique of Agarwal et al. We obtain improved upper bounds for s>=6, which are tight for even s up to lower-order terms in the exponent. More importantly, we also present a new technique for deriving upper bounds for lambda_s(n). With this new technique we: (1) re-derive the upper bound of lambda_3(n) <= 2n alpha(n) + O(n sqrt alpha(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 lambda_3(n) >= 2n alpha(n) - O(n), and therefore, the coefficient 2 is tight. We also present a simpler version of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds for even s>=4.

To appear in Journal of the ACM. 48 pages, 3 figures

References in corpus (1)

• Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture

Cited by in corpus (17)

• Lower bounds for weak epsilon-nets and stair-convexity
• New bounds on the maximum number of edges in $k$-quasi-planar graphs
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• Improved enumeration of simple topological graphs
• Sequences of formation width $4$ and alternation length $5$
• Three Generalizations of Davenport-Schinzel Sequences
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• Complexity of a Single Face in an Arrangement of s-Intersecting Curves
• On the VC-dimension of half-spaces with respect to convex sets
• Formations and generalized Davenport-Schinzel sequences
• The number of edges in k-quasi-planar graphs
• An algorithm for bounding extremal functions of forbidden sequences
• The 2-center problem and ball operators in strictly convex normed planes
• Disjoint edges in topological graphs and the tangled-thrackle conjecture
• Bounds for approximating lower envelopes with polynomials of degree at most $d$
• On the zone of a circle in an arrangement of lines
• Sequence saturation