## FANDOM

10,845 Pages

Davenport-Schinzel sequences are sequences that give rise to a hierarchy of functions that grow extremely close to linearly.[1]

An $$(n,s)$$ Davenport-Schinzel sequence is a sequence $$a_1,a_2,\ldots,a_m$$ where $$a_i$$ are integers in $$[1,n]$$, such that:

• $$a_i \neq a_{i+1}$$
• There is no sequence $$i_1 < i_2 < \cdots < i_{s + 2}$$ such that $$a_{i_1} = a_{i_3} = a_{i_5} = \ldots \neq a_{i_2} = a_{i_4} = a_{i_6} = \ldots$$.

Define $$\lambda_s(n)$$ as the length of the longest $$(n,s)$$ Davenport-Schinzel sequence. Then $$\lambda_1(n) = n$$, $$\lambda_2(n) = 2n - 1$$, $$\lambda_3(n) = \Theta(n\alpha(n))$$ where $$\alpha$$ is the inverse Ackermann function. A large number function can be extracted by defining $$\text{DS}_3(n) = \min\{m : \lambda_3(m) \geq mn\}$$.

### Sources Edit

1. http://www.ti.inf.ethz.ch/ew/lehre/CG09/materials/v19.pdf