• Title of article

    Grid classes and partial well order

  • Author/Authors

    Brignall، نويسنده , , Robert، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2012
  • Pages
    18
  • From page
    99
  • To page
    116
  • 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.
  • Keywords
    Permutation classes , Partial well-order , Grid classes , Infinite antichains
  • Journal title
    Journal of Combinatorial Theory Series A
  • Serial Year
    2012
  • Journal title
    Journal of Combinatorial Theory Series A
  • Record number

    1531723