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:
[img]
Preview
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (221Kb)
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.jcta.2011.08.005
Google Scholar: Look up in Google Scholar

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.

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
URI: http://oro.open.ac.uk/id/eprint/29444
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk