Random permutations turn universal at quadratic length: a log factor drops out, and Alon's weaker problem falls

A uniformly random permutation becomes universal once its length is quadratic, meaning it contains every shorter permutation as a pattern with high probability. The earlier result of He and Kwan required a length carrying an extra logarithmic factor; the new bound removes that factor. The theorem states that absolute constants exist such that for every sufficiently large integer, a uniformly random permutation fails with probability at most a negative power of that constant, hence is universal with high probability.

The proof first recasts the permutation question as a question about zero-one matrices, then searches for short pieces of each target permutation strip by strip. It builds on the interval-minor coupling of He and Kwan, which passes from the random permutation to an independent zero-one matrix. Each target permutation is split into ordered tuples of fixed length, searched in successive column strips, with an unfinished tuple retried in the next strip; bounding the overlap between test supports gives uniform control over all short tuples, and a deterministic counting argument then yields every target permutation without a union bound over all patterns.

The result concerns uniformly random permutations, requires sufficiently large length, and uses a constant chosen for convenience rather than the optimal one. Within the interval-minor framework the authors sketch how to reduce the constant to any value above a certain threshold, and identify the leading constant as a natural barrier for this approach.

The failure-probability bound comes from a limitation of the approach and is likely not sharp. The sharper failure estimate conjectured by He and Kwan is not reached, and the authors note that the current sufficient event cannot yield a super-linear failure exponent. The optimal constant remains open.