Geometric grid classes of permutations

DOI10.1090/S0002-9947-2013-05804-7zbMATH Open1271.05004arXiv1108.6319MaRDI QIDQ2849033FDOQ2849033

Authors: Mike Atkinson, Mathilde Bouvel, Michael Albert, N. Ruškuc, Vincent Vatter 

Publication date: 16 September 2013

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

rational generating functionsfinite sets of forbidden permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Permutations which are the union of an increasing and a decreasing subsequence
• Title not available (Why is that?)
• Title not available (Why is that?)
• On points drawn from a circle
• Combinatorics on traces
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Title not available (Why is that?)
• Sur l'extension aux relations de quelques propriétés des ordres
• Forbidden subsequences
• The X-class and almost-increasing permutations
• Profile classes and partial well-order for permutations
• Ordering by Divisibility in Abstract Algebras
• On partial well-order for monotone grid classes of permutations
• Grid classes and partial well order
• Partially well-ordered closed sets of permutations
• Restricted permutations
• Simple permutations and pattern restricted permutations
• A survey of simple permutations
• On growth rates of closed permutation classes
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Pattern avoidance classes and subpermutations
• Small permutation classes
• Pattern classes of permutations via bijections between linearly ordered sets
• Regular closed sets of permutations.
• Subclasses of the separable permutations

Cited In (38)

• On the effective and automatic enumeration of polynomial permutation classes
• Title not available (Why is that?)
• Combinatorial generation via permutation languages. I. Fundamentals
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• The micro-world of cographs
• Hereditary classes of graphs: a parametric approach
• Deciding atomicity of subword-closed languages
• Inflations of geometric grid classes of permutations
• Generating permutations with restricted containers
• The enumeration of permutations avoiding 3124 and 4312
• Letter Graphs and Geometric Grid Classes of Permutations
• Automatic discovery of structural rules of permutation classes
• Sorting via shuffles with a cut after the longest increasing prefix
• 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
• Square permutations are typically rectangular
• Enumerating indices of Schubert varieties defined by inclusions
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• The enumeration of three pattern classes using monotone grid classes
• On the centrosymmetric permutations in a class
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• 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
• Arc permutations
• On cyclic Schur-positive sets of permutations
• Bounds on the lettericity of graphs
• Rooted forests that avoid sets of permutations
• Title not available (Why is that?)
• Rationality for subclasses of 321-avoiding permutations
• Schur-positive sets of permutations via products and grid classes
• 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)