What is the threshold function n = f(k) for the event that a random permutation on n symbols contains all patterns on k

Definitions and mathematical statement

For $\pi\in S_n$ and $\sigma\in S_k$, say that $\pi$ contains $\sigma$ if some indices $i_1<\cdots<i_k$ have values in the same relative order as $\sigma$. A permutation is $k$-universal if it contains every element of $S_k$. Let $\Pi_n$ be uniformly distributed on $S_n$.

Determine the asymptotic threshold for $k$-universality as $k\to\infty$. In the standard formulation of Alon's conjecture, for every fixed $\varepsilon>0$, \[ \Pr\!\left(\Pi_{\lceil(1+\varepsilon)k^2/4\rceil} \text{ is }k\text{-universal}\right)\longrightarrow1. \] The matching lower-threshold obstruction is the increasing pattern: below $(1-\varepsilon)k^2/4$, the probability of universality tends to zero, by longest-increasing-subsequence asymptotics. The unresolved direction requires all $k!$ patterns simultaneously, not merely any one prescribed pattern.

Occurrences need not occupy consecutive positions, and their actual values need only agree in relative order. The parameter $k$ grows, rather than remaining fixed while $n$ tends to infinity. The collected Cooper entry writes $k^2/2$; the primary modern statement by He and Kwan specifies $k^2/4$. This definition records that explicit constant correction while retaining the source's question about the universality threshold.

Short English statement

Determine the threshold at which a uniformly random permutation contains every pattern of a growing size k; Alon’s standard conjectured scale is k²/4.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100083 (AMR-030-0083), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Probability, source-order bullet 83. Original source indexed by AMR-030-0083. https://people.math.sc.edu/cooper/combprob.html.
• S3 He and Kwan, Universality of random permutations, statement of Alon’s conjecture. https://arxiv.org/abs/1911.12878.