Geometric grid classes of permutations
From MaRDI portal
Publication:2849033
Abstract: A geometric grid class consists of those permutations that can be drawn on a specified set of line segments of slope pm1 arranged in a rectangular pattern governed by a matrix. Using a mixture of geometric and language theoretic methods, we prove that such classes are specified by finite sets of forbidden permutations, are partially well ordered, and have rational generating functions. Furthermore, we show that these properties are inherited by the subclasses (under permutation involvement) of such classes, and establish the basic lattice theoretic properties of the collection of all such subclasses.
Recommendations
- Inflations of geometric grid classes of permutations
- Letter graphs and geometric grid classes of permutations
- Geometric permutations
- Geometric sets of permutations
- Growth rates of geometric grid classes of permutations
- Enumeration of cyclic permutations in vector grid classes
- Grid classes and the Fibonacci dichotomy for restricted permutations
- Geometric permutations and two applications
- Letter graphs and geometric grid classes of permutations: characterization and recognition
Cites work
- scientific article; zbMATH DE number 53151 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 789816 (Why is no real title available?)
- scientific article; zbMATH DE number 3245483 (Why is no real title available?)
- A survey of simple permutations
- Analytic combinatorics
- Combinatorics on traces
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Forbidden subsequences
- Grid classes and partial well order
- Grid classes and the Fibonacci dichotomy for restricted permutations
- On growth rates of closed permutation classes
- On partial well-order for monotone grid classes of permutations
- On points drawn from a circle
- Ordering by Divisibility in Abstract Algebras
- Partially well-ordered closed sets of permutations
- Pattern avoidance classes and subpermutations
- Pattern classes of permutations via bijections between linearly ordered sets
- Permutations which are the union of an increasing and a decreasing subsequence
- Profile classes and partial well-order for permutations
- Regular closed sets of permutations.
- Restricted permutations
- Simple permutations and pattern restricted permutations
- Small permutation classes
- Subclasses of the separable permutations
- Sur l'extension aux relations de quelques propriétés des ordres
- The X-class and almost-increasing permutations
Cited in
(41)- \(2\times 2\) monotone grid classes are finitely based
- scientific article; zbMATH DE number 7559423 (Why is no real title available?)
- On the effective and automatic enumeration of polynomial permutation classes
- The micro-world of cographs
- Letter graphs and geometric grid classes of permutations: characterization and recognition
- Hereditary classes of graphs: a parametric approach
- Generating permutations with restricted containers
- Inflations of geometric grid classes of permutations
- The enumeration of permutations avoiding 3124 and 4312
- Deciding atomicity of subword-closed languages
- Automatic discovery of structural rules of permutation classes
- Combinatorial specifications for juxtapositions of permutation classes
- Sorting via shuffles with a cut after the longest increasing prefix
- Schur-positivity via products of grid classes
- Combinatorial generation via permutation languages. I: Fundamentals
- Permutation patterns in genome rearrangement problems: the reversal model
- Well-quasi-order for permutation graphs omitting a path and a clique
- Labelled well-quasi-order for permutation classes
- Enumerating indices of Schubert varieties defined by inclusions
- Square permutations are typically rectangular
- The enumeration of three pattern classes using monotone grid classes
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- On the centrosymmetric permutations in a class
- Letter graphs and geometric grid classes of permutations
- Enumeration of cyclic permutations in vector grid classes
- Growth rates of permutation grid classes, tours on graphs, and the spectral radius
- Growth rates of geometric grid classes of permutations
- Characterising inflations of monotone grid classes of permutations
- Letter graphs and modular decomposition
- Arc permutations
- On cyclic Schur-positive sets of permutations
- An antichain of monomial ideals in a twisted commutative algebra
- Bounds on the lettericity of graphs
- Rooted forests that avoid sets of permutations
- Schur-positive sets of permutations via products and grid classes
- Rationality for subclasses of 321-avoiding permutations
- On partial well-order for monotone grid classes of permutations
- Grid classes and partial well order
- Grid classes and the Fibonacci dichotomy for restricted permutations
- An algorithm computing combinatorial specifications of permutation classes
- Juxtaposing Catalan permutation classes with monotone ones
This page was built for publication: Geometric grid classes of permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849033)
