Grid classes and partial well order

DOI10.1016/J.JCTA.2011.08.005zbMATH Open1314.06002arXiv0906.3723OpenAlexW2005287322MaRDI QIDQ645965FDOQ645965

Authors: Robert Brignall 

Publication date: 11 November 2011

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

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.

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

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

zbMATH Keywords

partial well-ordergrid classesinfinite antichainspermutation classes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Geometric grid classes of permutations
• Title not available (Why is that?)
• Profile classes and partial well-order for permutations
• Well-quasi-order for permutation graphs omitting a path and a clique
• Labelled well-quasi-order for permutation classes
• Boundary properties of well-quasi-ordered sets of graphs
• On partial well-order for monotone grid classes of permutations
• Partially well-ordered closed sets of permutations
• 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)