  A permutation $\sigma\in S_n$ is said to be $k$-universal or a
$k$-superpattern if for every $\pi\in S_k$, there is a subsequence of $\sigma$
that is order-isomorphic to $\pi$. A simple counting argument shows that
$\sigma$ 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 $\sigma$. 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.
