pith. sign in

arxiv: 0906.3723 · v2 · pith:AAG4TO4Inew · submitted 2009-06-19 · 🧮 math.CO

Grid classes and partial well order

classification 🧮 math.CO
keywords classesgridcomponentconstructiondirectiongriddingmatrixonly
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.