Constructing sparse Davenport-Schinzel sequences

Abstract

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)=\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)$ for any alternation $u$ of length $s\ge 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 $\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 $\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.