On growth rates of closed permutation classes
This paper derives several quantitative estimates for closed permutation classes. ``A class of permutations \(\Pi\) is called closed if \(\pi\subset\sigma\in \Pi\) implies \(\pi\in\Pi\), where the relation \(\subset\) is the natural containment of permutations. (For example, the permutation \((3,5,4,2,1,7,8,6,9)\) contains \((2,1,3)\) but not \((3,1,2)\).) The well-known Stanley-Wilf conjecture can be reformulated as saying that any closed class of permutations different from the class of all permutations has at most exponential cardinality. The main result of this paper states roughly that the cardinality of any class of closed permutations is either bounded above polynomially or bounded below exponentially.
- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- Composability of permutation classes
- Generating permutations with restricted containers
- On the least exponential growth admitting uncountably many closed permutation classes
- Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
- Growth rates of permutation classes: categorization up to the uncountability threshold
- Permutation classes of polynomial growth
- On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- The orbit algebra of an oligomorphic permutation group with polynomial profile is Cohen-Macaulay
- \(k\)-pop stack sortable permutations and \(2\)-avoidance
- Jumps in speeds of hereditary properties in finite relational languages
- Classes of graphs without star forests and related graphs
- Geometric grid classes of permutations
- Young classes of permutations
- PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
- Growth Rates and Critical Exponents of Classes of Binary Combinatorial Geometries
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- scientific article; zbMATH DE number 1507230 (Why is no real title available?)
- Automatic discovery of structural rules of permutation classes
- Growth rates of geometric grid classes of permutations
- Two examples of Wilf-collapse
- On the centrosymmetric permutations in a class
- Wilf-collapse in permutation classes having two basis elements of size three
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- On the effective and automatic enumeration of polynomial permutation classes
- An Algorithm to Enumerate Grid Signed Permutation Classes
- Hereditary classes of ordered binary structures
- Stanley-Wilf limits for patterns in rooted labeled forests
- A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
- Labelled well-quasi-order in juxtapositions of permutation classes
- Embedding dualities for set partitions and for relational structures
- Ordered structures with no finite monomorphic decomposition: application to the profile of hereditary classes
- Enumerating polynomial colored permutation classes
- Intervals of permutation class growth rates
- Pin classes. II: Small pin classes
- Finding regular insertion encodings for permutation classes
- New records in Stanley-Wilf limits
- Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups
- Growth constants of minor-closed classes of graphs
This page was built for publication: On growth rates of closed permutation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1871365)
