Universality of random permutations

Abstract

It is a classical fact that for any $\epsilon >0$, a random permutation of length $n=(1+\epsilon )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=2000k^2\log \log k$ suffices.

Cited by in corpus (1)

• Universal arrays