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.
A finite sequence U = u1, u2, u3, is said to be a Davenport–Schinzel sequence of order s if it satisfies the following two properties:
For instance, the sequence
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.
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
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.
Using big O and big Θ notation, the following bounds are known:
...
Wikipedia