Grid classes and partial well order

DOI10.1016/J.JCTA.2011.08.005MaRDI QIDQ645965zbMATHOpenAlexFDO

Authors Robert Brignall

Publication date 11 November 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

partial well-ordergrid classesinfinite antichainspermutation classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07)

Abstract: We prove necessary and sufficient conditions on a family of (generalised) gridding matrices to determine when the corresponding permutation classes are partially well-ordered. One direction requires an application of Higman's Theorem and relies on there being only finitely many simple permutations in the only non-monotone cell of each component of the matrix. The other direction is proved by a more general result that allows the construction of infinite antichains in any grid class of a matrix whose graph has a component containing two or more non-monotone-griddable cells. The construction uses a generalisation of pin sequences to grid classes, together with a number of symmetry operations on the rows and columns of a gridding.

Recommendations

• On partial well-order for monotone grid classes of permutations
• Profile classes and partial well-order for permutations
• Geometric grid classes of permutations
• Partially well-ordered closed sets of permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations

Cites work

• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A survey of simple permutations
• Decomposing simple permutations, with enumerative consequences
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Finiteness theorems for graphs and posets obtained by compositions
• Geometric grid classes of permutations
• Graph minors. XX: Wagner's conjecture
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Minimal antichains in well-founded quasi-orders with an application to tournaments
• On partial well-order for monotone grid classes of permutations
• Ordering by Divisibility in Abstract Algebras
• Partially well-ordered closed sets of permutations
• Profile classes and partial well-order for permutations
• Simple permutations and pattern restricted permutations
• Small permutation classes
• The enumeration of permutations avoiding 2143 and 4231
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(9)

• On partial well-order for monotone grid classes of permutations
• Labelled well-quasi-order for permutation classes
• Boundary properties of well-quasi-ordered sets of graphs
• Profile classes and partial well-order for permutations
• Well-quasi-order for permutation graphs omitting a path and a clique
• Geometric grid classes of permutations
• Partially well-ordered closed sets of permutations
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• Juxtaposing Catalan permutation classes with monotone ones

This page was built for publication: Grid classes and partial well order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645965)