PreprintarXiv licencearXiv
Typical growth of the Füredi-Hajnal and Stanley-Wilf limits
Abstract
We prove that the Füredi-Hajnal limit and the Stanley-Wilf limit of a uniformly random permutation matrix of order k are at most exp(O(√k(log k)5/2)) with probability tending to one as k→∞. This improves the bound exp(O(k2/3(log k)7/3/(loglog k)1/3)) of Cibulka and Kynčl. Together with the lower bound due to Fox, these bounds show that the logarithms of both limits are k1/2+o(1) for almost all permutations.
Related
BibTeX
@misc{geneson2026typical,
title = {{Typical growth of the Füredi-Hajnal and Stanley-Wilf limits}},
author = {Jesse Geneson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02707},
eprint = {2610.02707},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02707},
}
RIS
TY - UNPB
TI - Typical growth of the Füredi-Hajnal and Stanley-Wilf limits
AU - Jesse Geneson
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02707
UR - https://arxiv.org/abs/2610.02707
AB - We prove that the Füredi-Hajnal limit and the Stanley-Wilf limit of a uniformly random permutation matrix of order k are at most exp(O(√k(log k)^5/2)) with probability tending to one as k→∞. This improves the bound exp(O(k^2/3(log k)^7/3/(loglog k)^1/3)) of Cibulka and Kynčl. Together with the lower bound due to Fox, these bounds show that the logarithms of both limits are k^1/2+o(1) for almost all permutations.
ER -