Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices

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\mathrm{/}t}\times n$ matrices containing $n^{1+1\mathrm{/}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)\mathrm{/}n\ge 2^s$ grows exponentially with $s$. When $s = n^{o(1)}$weshow$\lambda(s,n)/n \ge (\frac{s}{2\log\log_s n})^{\log\log_s n}$growsfasterthananypolynomialin$s$\mathrm{.}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.