The Open UniversitySkip to content

Grid classes and partial well order

Brignall, Robert (2012). Grid classes and partial well order. Journal of Combinatorial Theory, Series A, 119(1) pp. 99–116.

Full text available as:
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (221Kb)
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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.

Item Type: Journal Article
Copyright Holders: 2011 Elsevier Inc.
ISSN: 0097-3165
Keywords: permutation classes; grid classes; partial well-order; infinite antoichains
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 29444
Depositing User: Robert Brignall
Date Deposited: 15 Sep 2011 14:54
Last Modified: 09 Dec 2012 04:39
Share this page:


Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340