{"id":"arxiv/2610.13530","url":"https://arxiv.org/abs/2610.13530","tags":["math.CO"],"score":0,"title":"Quadratic-size Random Permutations are Universal","domain":"math.CO","source":"arxiv","authors":["Yu Chen","Yiting Wang"],"reviews":0,"subject":"math.CO","summary":"A permutation is $n$-universal if it contains every permutation of length $n$ as a pattern. We prove that a uniformly random permutation of length $32n^2$ is $n$-universal with probability at least $1-\\exp(-c n/\\log n)$, for an absolute constant $c>0$ and all sufficiently large $n$. This removes a $\\log\\log n$ factor from an earlier result of He and Kwan~\\cite{He-Kwan} and resolves an open problem of Alon~\\cite{Alon2016}. The proof was found by GPT-6 Pro.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}