PDF (Accepted Manuscript)
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
|DOI (Digital Object Identifier) Link:||http://doi.org/10.1016/j.jcta.2011.08.005|
|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.|
|Keywords:||permutation classes; grid classes; partial well-order; infinite antoichains|
|Academic Unit/Department:||Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
|Depositing User:||Robert Brignall|
|Date Deposited:||15 Sep 2011 14:54|
|Last Modified:||06 Aug 2016 03:27|
|Share this page:|
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.