Permutation classes need not have proper growth rates

@misc{pantone2026permutation,
  title = {{Permutation classes need not have proper growth rates}},
  author = {Jay Pantone and Vincent Vatter},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30369},
  eprint = {2610.30369},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30369},
}

TY  - UNPB
TI  - Permutation classes need not have proper growth rates
AU  - Jay Pantone
AU  - Vincent Vatter
PY  - 2026
DA  - 2026/10/21
PB  - arXiv
DO  - 10.48550/arxiv.2610.30369
UR  - https://arxiv.org/abs/2610.30369
AB  - By the Marcus-Tardos Theorem (formerly the Stanley-Wilf Conjecture), every permutation class other than the class of all permutations has a finite upper growth rate, meaning that the nth root of the number of permutations of length n in the class has a finite limit superior. It has long been conjectured that this limit superior is in fact always a proper limit. We disprove this by constructing a permutation class whose upper and lower growth rates differ. The construction uses grid classes with cubic row-column graphs of increasing girth, obtained from Haar graphs of finite 2-groups. The corresponding hereditary property of ordered graphs also disproves an analogous 2006 conjecture of Balogh, Bollobás, and Morris. Along the way, we show that every proper permutation class with a D-finite generating function has a proper growth rate. We also establish refined enumerative bounds for grid classes, which lead to a short proof of Albert and Vatter's generalization of Bevan's Theorem on the growth rates of grid classes.
ER  -