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 (226kB)
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 Item
Copyright Holders: 2011 Elsevier Inc.
ISSN: 0097-3165
Keywords: permutation classes; grid classes; partial well-order; infinite antoichains
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 29444
Depositing User: Robert Brignall
Date Deposited: 15 Sep 2011 14:54
Last Modified: 09 Dec 2018 05:20
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU