Permutation classes need not have proper growth rates
Jay Pantone, Vincent Vatter
Source abstract
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 th root of the number of permutations of length 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.