Inflations of geometric grid classes of permutations
From MaRDI portal
Publication:2339726
Abstract: Geometric grid classes and the substitution decomposition have both been shown to be fundamental in the understanding of the structure of permutation classes. In particular, these are the two main tools in the recent classification of permutation classes of growth rate less than (a specific algebraic integer at which infinite antichains begin to appear). Using language- and order-theoretic methods, we prove that the substitution closures of geometric grid classes are partially well-ordered, finitely based, and that all their subclasses have algebraic generating functions. We go on to show that the inflation of a geometric grid class by a strongly rational class is partially well-ordered, and that all its subclasses have rational generating functions. This latter fact allows us to conclude that every permutation class with growth rate less than has a rational generating function. This bound is tight as there are permutation classes with growth rate which have nonrational generating functions.
Recommendations
Cites work
- scientific article; zbMATH DE number 3492580 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 3198033 (Why is no real title available?)
- Analytic combinatorics
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Finiteness theorems for graphs and posets obtained by compositions
- Geometric grid classes of permutations
- Grid classes and the Fibonacci dichotomy for restricted permutations
- Growing at a perfect speed
- Hereditary properties of ordered graphs
- On free monoids partially ordered by embedding
- Ordering by Divisibility in Abstract Algebras
- Overview of some general results in combinatorial enumeration
- PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
- Regular closed sets of permutations.
- Simple permutations and algebraic generating functions
- Simple permutations and pattern restricted permutations
- Small permutation classes
- Subclasses of the separable permutations
- The enumeration of permutations with a prescribed number of ``forbidden patterns
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- Wreath products of permutation classes
Cited in
(18)- Geometric grid classes of permutations
- Letter graphs and geometric grid classes of permutations: characterization and recognition
- Growth rates of permutation classes: from countable to uncountable
- Intervals of permutation class growth rates
- Well-quasi-order for permutation graphs omitting a path and a clique
- Labelled well-quasi-order for permutation classes
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Letter graphs and geometric grid classes of permutations
- 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
- Characterising inflations of monotone grid classes of permutations
- Letter graphs and modular decomposition
- An antichain of monomial ideals in a twisted commutative algebra
- Bounds on the lettericity of graphs
- On graphs of sets of reduced words
- Rationality for subclasses of 321-avoiding permutations
- An algorithm computing combinatorial specifications of permutation classes
This page was built for publication: Inflations of geometric grid classes of permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339726)
