Partially Well-Ordered Closed Sets of Permutations |
| |
Authors: | Atkinson M. D. Murphy M. M. Ruškuc N. |
| |
Affiliation: | (1) Department of Computer Science, University of Otago, New Zealand;(2) School of Mathematics and Statistics, University of St Andrews, U.K. |
| |
Abstract: | 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. |
| |
Keywords: | finite basis involvement partial well-order pattern containment permutation |
本文献已被 SpringerLink 等数据库收录! |