Growth rates of permutation classes: from countable to uncountable

2019/05/09 by Vincent Vatter · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Mathematical Dynamics and Fractals #Advanced Combinatorial Mathematics #Uncountable set #Countable set #Permutation (music) #Mathematics #Algebraic number #Combinatorics #Property (philosophy) #Discrete mathematics #Cyclic permutation #Physics #Symmetric group

paper · doi:10.1112/plms.12250

openalex publication_date 2019/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

We establish that there is an algebraic number ξ ≈ 2.30522 such that while there are uncountably many growth rates of permutation classes arbitrarily close to ξ, there are only countably many less than ξ. Central to the proof are various structural notions regarding generalized grid classes and a new property of permutation classes called concentration. The classification of growth rates up to ξ is completed in a subsequent paper.

Citations

• Model Theory
• A Combinatorial Problem in Geometry
• Some general results in combinatorial enumeration
• Overview of some general results in combinatorial enumeration
• On the growth rate of 1324-avoiding permutations
• Transversals of 2-intervals, a topological approach
• Simple permutations and pattern restricted permutations
• Transitiv orientierbare Graphen
• Representations for real numbers and their ergodic properties
• Excluded permutation matrices and the Stanley–Wilf conjecture
• Intervals of Permutation Class Growth Rates
• Small permutation classes
• Growth rates of permutation classes: Categorization up to the uncountability threshold
• On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern

Cited by

• Stanley–Wilf conjecture [wikipedia]