Small permutation classes

DOI10.1112/PLMS/PDR017MaRDI QIDQ3102708zbMATH OpenOpenAlexFDO

Authors Vincent Vatter

Publication date 6 December 2011

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.4006

zbMATH Keywords

permutationshereditary propertiespermutation classesgrowth rates of permutation classespermutation containment order

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorics of partially ordered sets (06A07)

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).

Recommendations

• Small configurations in simple permutations
• Permutation classes
• Young classes of permutations
• scientific article; zbMATH DE number 1594288
• SUBGROUPS OF SMALL INDEX IN ORDERED PERMUTATION GROUPS
• On faithful permutation representations of small degree
• Simple primitive permutation groups of small degree
• Subclasses of the separable permutations
• scientific article; zbMATH DE number 1538179
• Set systems and families of permutations with small traces

Cited in

(32)

• Permutation classes of polynomial growth
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Geometric grid classes of permutations
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• An exact characterization of saturation for permutation matrices
• Growth rates of permutation classes: from countable to uncountable
• Set systems and families of permutations with small traces
• Classes of graphs without star forests and related graphs
• Prolific permutations
• Generating permutations with restricted containers
• Inflations of geometric grid classes of permutations
• An elementary proof of Bevan's theorem on the growth of grid classes of permutations
• Growth constants of minor-closed classes of graphs
• Automatic discovery of structural rules of permutation classes
• Intervals of permutation class growth rates
• Large infinite antichains of permutations
• On growth rates of permutations, set partitions, ordered graphs and other objects
• A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
• Well-quasi-order for permutation graphs omitting a path and a clique
• Labelled well-quasi-order for permutation classes
• Letter graphs and geometric grid classes of permutations
• Embedding dualities for set partitions and for relational structures
• On growth rates of closed permutation classes
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Growth rates of geometric grid classes of permutations
• Young classes of permutations
• An antichain of monomial ideals in a twisted commutative algebra
• Grid classes and partial well order
• Bounded affine permutations. I: Pattern avoidance and enumeration
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Juxtaposing Catalan permutation classes with monotone ones

Describes a project that uses

Uses Software

• OEIS
• InsEnc

This page was built for publication: Small permutation classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102708)