Origins of Nonlinearity in Davenport–Schinzel Sequences
Seth Pettie · SIAM Journal on Discrete Mathematics · 2011
A generalized Davenport–Schinzel sequence is one over a finite alphabet that excludes subsequences isomorphic to a fixed forbidden subsequence. The fundamental problem in this area is bounding the maximum length of such sequences. Following Klazar, we let $\mathrm{Ex}(\sigma,n)$ be the maximum length of a sequence over an n-letter alphabet excluding subsequences isomorphic to $\sigma$. It has been proved that for every $\sigma$, $\mathrm{Ex}(\sigma,n)$ is either linear or very close to linear. In particular it is $O(n2^{\alpha(n)^{O(1)}})$, where $\alpha$ is the inverse-Ackermann function and $O(1)$ depends on $\sigma$. In much the same way that the complete graphs $K_5$ and $K_{3,3}$ represent the minimal causes of nonplanarity, there must exist a set $\Phi_{Nonlin}$ of minimal nonlinear forbidden subsequences. Very little is known about the size or membership of $\Phi_{Nonlin}$. In this paper we construct an infinite antichain of nonlinear forbidden subsequences which, we argue, strongly supports the conjecture that $\Phi_{Nonlin}$ is itself infinite. Perhaps the most novel contribution of this paper is a succinct, humanly readable code for expressing the structure of forbidden subsequences.