Constructing sparse Davenport-Schinzel sequences

For any sequence $u$, the extremal function $Ex(u,j,n)$ is the maximum possible length of a $j$-sparse sequence with $n$ distinct letters that avoids $u$. We prove that if $u$ is an alternating sequence $abab\dots$ of length $s$, then $Ex(u,j,n)=\mathrm{\Theta }(s{n}^2)$ for all $j\ge 2$ and $s\ge n$, answering a question of Wellman and Pettie [Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices, Disc. Math. 341 (2018), 1987–1993] and extending the result of Roselle and Stanton that $Ex(u, 2, n) = \Theta(s n^2)$foranyalternation$u$oflength$s \geq n$ [Some properties of Davenport-Schinzel sequences, Acta Arithmetica 17 (1971), 355–362]. Wellman and Pettie also asked how large must $s(n)$ be for there to exist $n$-block $DS(n,s(n))$ sequences of length $\mathrm{\Omega }(n^{2-o(1)})$. We answer this question by showing that the maximum possible length of an $n$-block $DS(n,s(n))$ sequence is $\mathrm{\Omega }(n^{2-o(1)})$ if and only if $s(n) = \Omega(n^{1-o(1)})$. We also show related results for extremal functions of forbidden 0-1 matrices with any constant number of rows and extremal functions of forbidden sequences with any constant number of distinct letters.