Davenport–Schinzel sequence

In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following Atallah (1985) these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.^[1]

Definition

A finite sequence U = u₁, u₂, u₃, is said to be a Davenport–Schinzel sequence of order s if it satisfies the following two properties:

1. No two consecutive values in the sequence are equal to each other.
2. If x and y are two distinct values occurring in the sequence, then the sequence does not contain a subsequence ... x, ... y, ..., x, ..., y, ... consisting of s + 2 values alternating between x and y.

For instance, the sequence

1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3

is a Davenport–Schinzel sequence of order 3: it contains alternating subsequences of length four, such as ...1, ... 2, ... 1, ... 2, ... (which appears in four different ways as a subsequence of the whole sequence) but it does not contain any alternating subsequences of length five.

If a Davenport–Schinzel sequence of order s includes n distinct values, it is called an (n,s) Davenport–Schinzel sequence, or a DS(n,s)-sequence.^[2]

Length bounds

The complexity of DS(n,s)-sequence has been analyzed asymptotically in the limit as n goes to infinity, with the assumption that s is a fixed constant, and nearly tight bounds are known for all s. Let λ_s(n) denote the length of the longest DS(n,s)-sequence. The best bounds known on λ_s involve the inverse Ackermann function

α(n) = min { m | A(m,m) ≥ n },

where A is the Ackermann function. Due to the very rapid growth of the Ackermann function, its inverse α grows very slowly, and is at most four for problems of any practical size.^[3]

Using big O and big Θ notation, the following bounds are known:

• ${\displaystyle \lambda _{0}(n)=1}$ .
• ${\displaystyle \lambda _{1}(n)=n}$ .^[4]
• ${\displaystyle \lambda _{2}(n)=2n-1}$ .^[4]
• ${\displaystyle \lambda _{3}(n)=2n\alpha (n)+O(n)}$ .^[5] This complexity bound can be realized to within a factor of 2 by line segments: there exist arrangements of n line segments in the plane whose lower envelopes have complexity Ω(n α(n)).^[6]
• ${\displaystyle \lambda _{4}(n)=\Theta (n2^{\alpha (n)})}$ .^[7]
• ${\displaystyle \lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)})}$ .^[8]
• For both even and odd values of s ≥ 6,

${\displaystyle \lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}+O(\alpha (n)^{t-1})}}$ , where ${\displaystyle t=\left\lfloor {\frac {s-2}{2}}\right\rfloor }$ .^[9]

The value of λ_s(n) is also known when s is variable but n is a small constant:^[10]

${\displaystyle \lambda _{s}(1)=1\,}$ 

${\displaystyle \lambda _{s}(2)=s+1\,}$ 

${\displaystyle \lambda _{s}(3)=3s-2+(s{\bmod {2}})}$ 

${\displaystyle \lambda _{s}(4)=6s-2+(s{\bmod {2}}).}$ 

When s is a function of n the upper and lower bounds on Davenport-Schinzel sequences are not tight.

• When ${\displaystyle s>n^{1/t}(t-1)!}$ , ${\displaystyle \lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)}$  and ${\displaystyle \lambda _{s}(n)=O(n^{2}s)}$ .^[11]
• When ${\displaystyle \log \log n<s=n^{o(1)}}$ , ${\displaystyle \lambda _{s}(n)=\Omega \left(n\left({\frac {s}{2\log \log _{s}n}}\right)^{\log \log _{s}n}\right)}$ .^[12]
• When ${\displaystyle s\leq \log \log n}$ , ${\displaystyle \lambda _{s}(n)=\Omega (n2^{s})}$ .^[13]

Application to lower envelopes

 

A Davenport–Schinzel sequence of order 3 formed by the lower envelope of line segments.

The lower envelope of a set of functions ƒ_i(x) of a real variable x is the function given by their pointwise minimum:

ƒ(x) = min_iƒ_i(x).

Suppose that these functions are particularly well behaved: they are all continuous, and any two of them are equal on at most s values. With these assumptions, the real line can be partitioned into finitely many intervals within which one function has values smaller than all of the other functions. The sequence of these intervals, labeled by the minimizing function within each interval, forms a Davenport–Schinzel sequence of order s. Thus, any upper bound on the complexity of a Davenport–Schinzel sequence of this order also bounds the number of intervals in this representation of the lower envelope.

In the original application of Davenport and Schinzel, the functions under consideration were a set of different solutions to the same homogeneous linear differential equation of order s. Any two distinct solutions can have at most s values in common, so the lower envelope of a set of n distinct solutions forms a DS(n,s)-sequence.

The same concept of a lower envelope can also be applied to functions that are only piecewise continuous or that are defined only over intervals of the real line; however, in this case, the points of discontinuity of the functions and the endpoints of the interval within which each function is defined add to the order of the sequence. For instance, a non-vertical line segment in the plane can be interpreted as the graph of a function mapping an interval of x values to their corresponding y values, and the lower envelope of a collection of line segments forms a Davenport–Schinzel sequence of order three because any two line segments can form an alternating subsequence with length at most four.

See also

• Squarefree word

Notes

1. Sharir & Agarwal (1995), pp. x and 2.
2. See Sharir & Agarwal (1995), p. 1, for this notation.
3. Sharir & Agarwal (1995), p. 14.
4. Sharir & Agarwal (1995), p. 6.
5. Sharir & Agarwal (1995), Chapter 2, pp. 12–42; Hart & Sharir (1986); Komjáth (1988); Klazar (1999); Nivasch (2009); Pettie (2015).
6. Sharir & Agarwal (1995), Chapter 4, pp. 86–114; Wiernik & Sharir (1988).
7. Sharir & Agarwal (1995), Chapter 3, pp. 43–85; Agarwal, Sharir & Shor (1989); Nivasch (2009); Pettie (2015).
8. Pettie (2015).
9. Sharir & Agarwal (1995), Chapter 3, pp. 43–85; Agarwal, Sharir & Shor (1989); Nivasch (2009); Pettie (2015).
10. Roselle & Stanton (1971).
11. Roselle & Stanton (1971); Wellman & Pettie (2016).
12. Wellman & Pettie (2016).
13. Wellman & Pettie (2016).

References

• Agarwal, P. K.; Sharir, Micha; Shor, P. (1989), "Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences", Journal of Combinatorial Theory, Series A, 52 (2): 228–274, doi:10.1016/0097-3165(89)90032-0, MR 1022320.
• Atallah, Mikhail J. (1985), "Some dynamic computational geometry problems", Computers and Mathematics with Applications, 11 (12): 1171–1181, doi:10.1016/0898-1221(85)90105-1, MR 0822083.
• Davenport, H.; Schinzel, Andrzej (1965), "A combinatorial problem connected with differential equations", American Journal of Mathematics, 87 (3), The Johns Hopkins University Press: 684–694, doi:10.2307/2373068, JSTOR 2373068, MR 0190010.
• Hart, S.; Sharir, Micha (1986), "Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes", Combinatorica, 6 (2): 151–177, CiteSeerX 10.1.1.295.885, doi:10.1007/BF02579170, MR 0875839, S2CID 18864716.
• Klazar, M. (1999), "On the maximum lengths of Davenport–Schinzel sequences", Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, American Mathematical Society, pp. 169–178.
• Komjáth, Péter (1988), "A simplified construction of nonlinear Davenport–Schinzel sequences", Journal of Combinatorial Theory, Series A, 49 (2): 262–267, doi:10.1016/0097-3165(88)90055-6, MR 0964387.
• Mullin, R. C.; Stanton, R. G. (1972), "A map-theoretic approach to Davenport-Schinzel sequences.", Pacific Journal of Mathematics, 40: 167–172, doi:10.2140/pjm.1972.40.167, MR 0302601.
• Nivasch, Gabriel (2009), "Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations", (PDF), vol. 57, pp. 1–10, arXiv:0807.0484, Bibcode:2008arXiv0807.0484N, doi:10.1145/1706591.1706597, S2CID 3175575, archived from the original (PDF) on 2012-10-18, retrieved 2009-01-08.
• Roselle, D. P.; Stanton, R. G. (1971), "Some properties of Davenport-Schinzel sequences", Acta Arithmetica, 17 (4): 355–362, doi:10.4064/aa-17-4-355-362, MR 0284414.
• Sharir, Micha; Agarwal, Pankaj K. (1995), Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, ISBN 0-521-47025-0.
• Stanton, R. G.; Dirksen, P. H. (1976), "Davenport-Schinzel sequences.", Ars Combinatoria, 1 (1): 43–51, MR 0409347.
• Stanton, R. G.; Roselle, D. P. (1970), "A result on Davenport-Schinzel sequences", Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969), Amsterdam: North-Holland, pp. 1023–1027, MR 0304189.
• Wiernik, Ady; Sharir, Micha (1988), "Planar realizations of nonlinear Davenport–Schinzel sequences by segments", Discrete & Computational Geometry, 3 (1): 15–47, doi:10.1007/BF02187894, MR 0918177.
• Pettie, Seth (2015), "Sharp bounds on Davenport-Schinzel sequences of every order", J. ACM, 62 (5): 1–40, arXiv:1204.1086, doi:10.1145/2794075, S2CID 6880266.
• Wellman, Julian; Pettie, Seth (2016), Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices, arXiv:1610.09774, Bibcode:2016arXiv161009774W.

External links

• Davenport-Schinzel Sequence, from MathWorld.
• Davenport-Schinzel Sequences 2020-01-13 at the Wayback Machine, a section in the book Motion Planning, by Steven M. LaValle.