Profile classes and partial well-order for permutations

Details Profile classes and partial well-order for permutations Profile classes and partial well-order for permutations

2003-10-20

arxiv.org/abs/math/0310321v1

Mathematics

Combinatorics

30 pages, 8 figures

Scientific paper

It is known that the set of permutations, under the pattern containment ordering, is not a partial well-order. Characterizing the partially well-ordered closed sets (equivalently: down sets or ideals) in this poset remains a wide-open problem. Given a 0/+-1 matrix M, we define a closed set of permutations called the profile class of M. These sets are generalizations of sets considered by Atkinson, Murphy, and Ruskuc. We show that the profile class of M is partially well-ordered if and only if a related graph is a forest. Related to the antichains we construct to prove one of the directions of this result, we construct exotic fundamental antichains, which lack the periodicity exhibited by all previously known fundamental antichains of permutations.

Affiliated with

Also associated with

No associations

Rating

Profile classes and partial well-order for permutations 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 Profile classes and partial well-order for permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Profile classes and partial well-order for permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-421257