Small permutation classes

Abstract

We establish a phase transition for permutation classes (downsets of permutations under the permutation containment order): there is an algebraic number $\kappa$, approximately 2.20557, for which there are only countably many permutation classes of growth rate (Stanley-Wilf limit) less than $\kappa$ but uncountably many permutation classes of growth rate $\kappa$, answering a question of Klazar. We go on to completely characterize the possible sub-$\kappa$ growth rates of permutation classes, answering a question of Kaiser and Klazar. Central to our proofs are the concepts of generalized grid classes (introduced herein), partial well-order, and atomicity (also known as the joint embedding property).

References in corpus (1)

• Overview of some general results in combinatorial enumeration

Cited by in corpus (19)

• Permutation classes of every growth rate above 2.48188
• Overview of some general results in combinatorial enumeration
• Inflations of geometric grid classes of permutations
• An Erdős--Hajnal analogue for permutation classes
• The permutation class Av(4213,2143)
• Geometric grid classes of permutations
• Growth rates of geometric grid classes of permutations
• An exact characterization of saturation for permutation matrices
• On partial well-order for monotone grid classes of permutations
• Grid classes and partial well order
• Intervals of permutation class growth rates
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• Polynomial Bounds on the Slicing Number
• A counterexample to a Gröbner approach for noetherianity of the twisted commutative algebra $\mathrm{Sym}({\mathrm{Sym}}^2({\mathbf{C}}^{\infty }))$
• Juxtaposing Catalan permutation classes with monotone ones
• $2\times 2$ monotone grid classes are finitely based
• Enumeration of permutations indexing local complete intersection Schubert varieties
• Patterns in Permutations and Involutions: A Structural and Enumerative Approach
• Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique