Geodesic
Profile classes and partial well-order for permutations
The electronic journal of combinatorics, Permutation Patterns, Tome 9 (2002) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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/\pm1$ 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 Ruškuc. 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.
DOI : 10.37236/1689
Classification : 06A07, 68R05, 06A06, 05A05
Mots-clés : restricted permutation, forbidden subsequence, partial well-order, well-quasi-order 
@article{10_37236_1689,
     author = {Maximillian M. Murphy and Vincent R. Vatter},
     title = {Profile classes and partial well-order for permutations},
     journal = {The electronic journal of combinatorics},
     year = {2002},
     volume = {9},
     number = {2},
     doi = {10.37236/1689},
     zbl = {1034.06005},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1689/}
}
TY  - JOUR
AU  - Maximillian M. Murphy
AU  - Vincent R. Vatter
TI  - Profile classes and partial well-order for permutations
JO  - The electronic journal of combinatorics
PY  - 2002
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1689/
DO  - 10.37236/1689
ID  - 10_37236_1689
ER  - 
%0 Journal Article
%A Maximillian M. Murphy
%A Vincent R. Vatter
%T Profile classes and partial well-order for permutations
%J The electronic journal of combinatorics
%D 2002
%V 9
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/1689/
%R 10.37236/1689
%F 10_37236_1689
Maximillian M. Murphy; Vincent R. Vatter. Profile classes and partial well-order for permutations. The electronic journal of combinatorics, Permutation Patterns, Tome 9 (2002) no. 2. doi: 10.37236/1689

Cité par Sources :