zbMATH — the first resource for mathematics

Profile classes and partial well-order for permutations. (English) Zbl 1034.06005
Electron. J. Comb. 9, No. 2, Research paper R17, 30 p. (2002-2003); printed version J. Comb. 9, No. 2, R17 (2002-2003).
Summary: 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/\pm 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.

06A07 Combinatorics of partially ordered sets
68R05 Combinatorics in computer science
06A06 Partial orders, general
05A05 Permutations, words, matrices
Full Text: EMIS EuDML arXiv