2009/06/19 by Robert Brignall, Brignall, Robert
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0906.3723
openalex publication_date 2009/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.