  It is a classical fact that for any $\varepsilon > 0$, a random permutation
of length $n = (1 + \varepsilon) k^2 / 4$ typically contains a monotone
subsequence of length $k$. As a far-reaching generalization, Alon conjectured
that a random permutation of this same length $n$ is typically $k$-universal,
meaning that it simultaneously contains every pattern of length $k$. He also
made the simple observation that for $n = O(k^2 \log k)$, a random length-$n$
permutation is typically $k$-universal. We make the first significant progress
towards Alon's conjecture by showing that $n = 2000 k^2 \log \log k$ suffices.
