Paper detail

Lower bounds for superpatterns and universal sequences

A permutation $σ\in S_n$ is said to be $k$-universal or a $k$-superpattern if for every $π\in S_k$, there is a subsequence of $σ$ that is order-isomorphic to $π$. A simple counting argument shows that $σ$ can be a $k$-superpattern only if $n\ge (1/e^2+o(1))k^2$, and Arratia conjectured that this lower bound is best-possible. Disproving Arratia's conjecture, we improve the trivial bound by a small constant factor. We accomplish this by designing an efficient encoding scheme for the patterns that appear in $σ$. This approach is quite flexible and is applicable to other universality-type problems; for example, we also improve a bound by Engen and Vatter on a problem concerning $(k+1)$-ary sequences which contain all $k$-permutations.