Asymptotic Tightness of the Pigeonhole Bound for Large-Order Davenport-Schinzel Sequences

Abstract

We prove that the pigeonhole upper bound $\lambda (s,m)\le \left(\genfrac{}{}{0ex}{}{m}{2}\right)(s+1)$ is asymptotically tight whenever $s/\sqrt{m}\to \infty$. In particular, $\lambda (s,m)\sim \left(\genfrac{}{}{0ex}{}{m}{2}\right)s$ in this regime. As corollaries: $\lambda (n,n)/n^3\to \frac{1}{2}$, resolving the leading constant from the previously known interval $[\frac{1}{3},\frac{1}{2}]$; and more generally $\lambda (an,bn)\sim \frac{a{b}^2}{2}{n}^3$ for any constants $a,b>0$.