pith. sign in

arxiv: math/0310321 · v1 · submitted 2003-10-20 · 🧮 math.CO

Profile classes and partial well-order for permutations

classification 🧮 math.CO
keywords permutationssetsantichainsprofileclassclosedconstructfundamental
0
0 comments X
read the original abstract

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.

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.