2003/10/20 by Maximillian Murphy, Murphy, Maximillian, Vincent Vatter +1
Mathematics · #06A06 (Primary) 06A07 #68R15 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:06A06 #msc:06A07 #msc:68R15
paper · pdf · doi:10.48550/arxiv.math/0310321
30 pages, 8 figures
arxiv created 2003/10/20 · arxiv updated 2009/12/01
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.