Small permutation classes
By Vincent Vatter. 2007
67 citations recorded by the source corpus.
We establish a phase transition for permutation classes (downsets of permutations under the permutation containment order): there is an algebraic number κ, approximately 2.20557, for which there are only countably many permutation classes of growth rate (Stanley–Wilf limit) less than κ but uncountably many permutation classes of growth rate κ, answering a question of Klazar. We go on to completely characterize the possible sub‐κ 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, the substitution decomposition, and atomicity (a.k.a. the joint embedding property).
Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/e9fd462222c158e23444b848821059bb34c8a4d0
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- Permutation classes (2014, background): “We prove this result by appealing to a result of Gyárfás and Lehel from 1970, but a proof from first principles can be found in Vatter [161].”
- Geometric grid classes of permutations (2011, background): “…the first programme, we point to the work of Kaiser and Klazar [20], who characterised the possible growth rates up to 2, and the work of Vatter [25], who extended this characterisation up to the algebraic number κ ≈ 2.20557, the point at which infinite antichains begin to emerge, and where the…”