Phân loại các lớp học

Một hoán vị? được cho là một subpermutation của một hoán vị? (Hoặc được tham gia vào) Nếu? có một dãy được sắp xếp trong cùng một cách tương đối. Đối với ví dụ 231là một subpermutation của 35412 vì 351 dãy của nó có cùng một khuôn mẫutạp chí điện tử của tổ hợp 12 (2005), # R31 1là 231. Chúng tôi nói như vậy? tránh? nếu? không phải là một subpermutation?. Lý thuyết phát triểncác mô hình hoán vị là một phần thành lập tổ hợp (xem, ví dụ,[12]).Lý thuyết này đã được thúc đẩy bởi việc nghiên...
Nội dung trích xuất từ tài liệu:
Phân loại các lớp học Sorting classes M. H. Albert R. E. L. Aldred Department of Computer Science Department of Mathematics and Statistics University of Otago University of Otago malbert@cs.otago.ac.nz raldred@math.otago.ac.nz M. D. Atkinson C. C. Handley Department of Computer Science Department of Computer Science University of Otago University of Otago mike@cs.otago.ac.nz chandley@cs.otago.ac.nz D. A. Holton D. J. McCaughan Department of Mathematics and Statistics Department of Mathematics and Statistics University of Otago University of Otago dholton@math.otago.ac.nz dmccaughan@math.otago.ac.nz H. van Ditmarsch Department of Computer Science University of Otago hans@cs.otago.ac.nz Submitted: Dec 20, 2004; Accepted: Jun 17, 2005; Published: Jun 26, 2005 Mathematics Subject Classifications: 05A15, 05A16 Abstract Weak and strong sorting classes are pattern-closed classes that are also closed downwards under the weak and strong orders on permutations. They are studied using partial orders that capture both the subpermutation order and the weak or strong order. In both cases they can be characterised by forbidden permutations in the appropriate order. The connection with the corresponding forbidden permuta- tions in pattern-closed classes is explored. Enumerative results are found in both cases.1 IntroductionA permutation π is said to be a subpermutation of a permutation σ (or to be involved inσ ) if σ has a subsequence that is ordered in the same relative way as π . For example 231is a subpermutation of 35412 because of its subsequence 351 which has the same patternthe electronic journal of combinatorics 12 (2005), #R31 1as 231. We say that σ avoids π if π is not a subpermutation of σ . The developing theoryof permutation patterns is now a well-established part of combinatorics (see, for example,[12]). This theory was originally motivated by the study of the sortable permutations asso-ciated with various computing devices (abstract data types such as stacks and deques [8],token passing networks [3], or hardware switches [2]). All these devices have the propertythat, if they are able to sort a sequence σ , then they are able to sort any subsequenceof σ . This subsequence property (that subsequences of sortable sequences are themselvessortable) is a very natural one to postulate of a sorting device. It is exactly this propertythat guarantees that the set of sortable permutations is closed under taking subpermu-tations. But there are other natural properties that a sorting device might have. Weare particularly interested in the following two. Both of them reflect the idea that “moresorted” versions of sortable sequences should themselves be sortable. 1. If s1 s2 . . . sn is sortable and si > si+1 then s1 s2 . . . si−1 si+1 si . . . sn is sortable, and 2. If s1 s2 . . . sn is sortable and si > sj where i < j then s1 s2 . . . si−1 sj si+1 . . . sj −1si sj +1 . . . sn is sortable. For the moment we call these the weak and strong exchange properties (the secondobviously implies the first). The weak exchange property would hold for sorting devicesthat operated by exchanging adjacent out of order pairs while the strong exchange prop-erty would hold if arbitrary out of order pairs could be exchanged. Our paper is aboutthe interaction between each of these properties and the subsequence property. We shall study this interaction using various (partial) orders on the set Ω of all (finite)permutations. Since we shall be considering several partial orders on Ω we shall writeσ P τ when we mean that σ ≤ τ in the partial order P ; this avoids the confusion of thesymbol “≤” being adorned by various subscripts. In the same spirit we write σ P τ tomean σ ≤ τ in P . All the partial orders we study will satisfy the minimum condition (that is, all properlydescending chains are finite) and we shall assume this from now on. If P is a partial order on Ω the lower ideals of P are those subsets X of Ω with theproperty β ∈ X and α P β =⇒ ...