Skip to content
DraconiticResearch
Search Sources API
185,139 studies31 sourcesUpdated 55 min ago
PreprintCC BY-NC-SA 4.0arXiv

Quadratic-size Random Permutations are Universal

  • Yu Chen
  • Yiting Wang
Open at sourcePDFDOICite

Abstract

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 32n2 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 loglog 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.

Related

  1. On some Non-Permutations of Quadratic Extension of Finite Field
    Bidushi Sharma, Dhiren Kumar Basnet
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension
    Hiroki Fukui
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori
    Tim Gerlach, Elizabeth Hartung, Pia Herkenrath +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Effect-Size Estimation and Confounding-Aware Permutations for PERMANOVA
    Sithija Manage, Emma Accorsi, Jacob Nearing +3
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  5. Permutations from ranking independent random variables
    Luke Turvey
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026quadraticsize,
  title = {{Quadratic-size Random Permutations are Universal}},
  author = {Yu Chen and Yiting Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.13530},
  eprint = {2610.13530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.13530},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Quadratic-size Random Permutations are Universal
AU  - Yu Chen
AU  - Yiting Wang
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.13530
UR  - https://arxiv.org/abs/2610.13530
AB  - 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 loglog 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.
ER  -