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.

DOI: https://doi.org/10.1016/j.jcta.2011.08.005

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 29444
• Item Type
• Journal Item
• ISSN
• 0097-3165
• Keywords
• permutation classes; grid classes; partial well-order; infinite antoichains
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2011 Elsevier Inc.
• Depositing User
• Robert Brignall