Partially well-ordered closed sets of permutations

被引：35
作者：
Atkinson, MD
Murphy, MM
Ruskuc, N
机构：
[1] Univ Otago, Dept Comp Sci, Dunedin, New Zealand
[2] Univ St Andrews, Sch Math & Stat, St Andrews, Fife, Scotland
来源：
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 2002年 / 19卷 / 02期
关键词：
finite basis; involvement; partial well-order; pattern containment; permutation;
D O I：
10.1023/A:1016500300436
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It is known that the "pattern containment" order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.
引用
收藏
页码：101 / 113
页数：13
相关论文
共 19 条
[1]  
Atkinson M. D., 1998, ELECT J COMBIN, V5
[2]   Generalized stack permutations [J].
Atkinson, MD .
COMBINATORICS PROBABILITY & COMPUTING, 1998, 7 (03) :239-246
[3]   Restricted permutations [J].
Atkinson, MD .
DISCRETE MATHEMATICS, 1999, 195 (1-3) :27-38
[4]  
ATKINSON MD, 1999, UNPUB RESTRICTED PER
[5]  
ATKINSON MD, UNPUB FINITENESS CON
[6]   Pattern matching for permutations [J].
Bose, P ;
Buss, AF ;
Lubiw, A .
INFORMATION PROCESSING LETTERS, 1998, 65 (05) :277-283
[7]  
Cohen D. I. A., 1978, Basic techniques of combinatorial theory
[8]  
Higman G., 1952, Proc. Lond. Math. Soc., V2, P326, DOI 10.1112/plms/s3-2.1.326
[9]  
KNUTH D, 1967, FUNDAMENTAL ALGORITH, V1
[10]   CRITERION FOR SMOOTHNESS OF SCHUBERT VARIETIES IN SL(N)/B [J].
LAKSHMIBAI, V ;
SANDHYA, B .
PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 1990, 100 (01) :45-52
12