Inflations of geometric grid classes of permutations

DOI10.1007/S11856-014-1098-8zbMATH Open1310.05005arXiv1202.1833OpenAlexW1993476439MaRDI QIDQ2339726FDOQ2339726

Authors: N. Ruškuc, Vincent Vatter, Michael Albert 

Publication date: 2 April 2015

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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 $kappaapprox2.20557$ (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 $kappa$ has a rational generating function. This bound is tight as there are permutation classes with growth rate $kappa$ which have nonrational generating functions.

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

Recommendations

• Geometric grid classes of permutations
• Growth rates of geometric grid classes of permutations
• Small permutation classes
• Growth rates of permutation classes: from countable to uncountable
• Growth rates of permutation classes: categorization up to the uncountability threshold

zbMATH Keywords

rational generating functionspermutation classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Title not available (Why is that?)
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Ordering by Divisibility in Abstract Algebras
• On free monoids partially ordered by embedding
• Simple permutations and pattern restricted permutations
• Overview of some general results in combinatorial enumeration
• Title not available (Why is that?)
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Geometric grid classes of permutations
• Wreath products of permutation classes
• Simple permutations and algebraic generating functions
• Small permutation classes
• Finiteness theorems for graphs and posets obtained by compositions
• Hereditary properties of ordered graphs
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Growing at a perfect speed
• Regular closed sets of permutations.
• Subclasses of the separable permutations

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
• Letter graphs and modular decomposition
• Characterising inflations of monotone grid classes of permutations
• 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)