Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices

Abstract

An order-$s$ Davenport-Schinzel sequence over an $n$-letter alphabet is one avoiding immediate repetitions and alternating subsequences with length $s+2$. The main problem is to determine the maximum length of such a sequence, as a function of $n$ and $s$. When $s$ is fixed this problem has been settled but when $s$ is a function of $n$, very little is known about the extremal function $\lambda (s,n)$ of such sequences. In this paper we give a new recursive construction of Davenport-Schinzel sequences that is based on dense 0-1 matrices avoiding large all-1 submatrices (aka Zarankiewicz's Problem.) In particular, we give a simple construction of $n^{2/t}\times n$ matrices containing $n^{1+1/t}$ 1s that avoid $t\times 2$ all-1 submatrices. Our lower bounds on $\lambda (s,n)$ exhibit three qualitatively different behaviors depending on the size of $s$ relative to $n$. When $s\le \log \log n$ we show that $\lambda (s,n)/n\ge 2^s$ grows exponentially with $s$. When $s=n^{o(1)}$ we show $\lambda (s,n)/n\ge (\frac{s}{2\log {\log }_{s}n}{)}^{\log {\log }_{s}n}$ grows faster than any polynomial in $s$. Finally, when $s=\Omega (n^{1/t}(t-1)!)$, $\lambda (s,n)=\Omega (n^{2}s/(t-1)!)$ matches the trivial upper bound $O(n^{2}s)$ asymptotically, whenever $t$ is constant.