tailieunhanh - Báo cáo toán học: "Profile classes and partial well-order for permutations"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Profile classes and partial well-order for permutations | Profile classes and partial well-order for permutations Maximillian M. Murphy School of Mathematics and Statistics University of St. Andrews Scotland max@ Vincent R. Vatter Department of Mathematics Rutgers University USA vatter@ Submitted May 3 2003 Accepted Oct 13 2003 Published Oct 23 2003 MR Subject Classifications 06A06 06A07 68R15 Keywords Restricted permutation forbidden subsequence partial well-order well-quasi-order 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. 1 Introduction It is an old and oft rediscovered fact that there are infinite antichains of permutations with respect to the pattern containment ordering so the set of all finite permutations is not partially well-ordered. Numerous examples exist including Laver 10 Pratt 13 Tarjan 17 and Spielman and Bona 16 . In order to show that certain subsets of permutations are partially well-ordered Atkinson Murphy and Ruskuc 3 introduced profile Partially supported by an NSF VIGRE grant to the Rutgers University Department of Mathematics. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2003 R17 1 classes of 0 1 vectors although they gave these classes a different name . We extend their definition to 0 1 matrices give a simple method of determining whether such a profile class is .