  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^2s)$ asymptotically, whenever $t$ is constant.
