FANDOM


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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.