Grid classes and partial well order

Details Grid classes and partial well order Grid classes and partial well order

2009-06-19

arxiv.org/abs/0906.3723v2

Mathematics

Combinatorics

22 pages, 7 figures. To appear in J. Comb. Theory Series A

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Grid classes and partial well order does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Grid classes and partial well order, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grid classes and partial well order will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-402162