Permutation groups arising from pattern involvement
- PDF / 667,711 Bytes
- 48 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 245 Views
Permutation groups arising from pattern involvement Erkko Lehtonen1 Received: 11 February 2019 / Accepted: 6 September 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract For an arbitrary finite permutation group G, subgroup of the symmetric group S , we determine the permutations involving only members of G as -patterns, i.e. avoiding all patterns in the set S \G. The set of all n-permutations with this property constitutes again a permutation group. We consequently refine and strengthen the classification of sets of permutations closed under pattern involvement and composition that is due to Atkinson and Beals. Keywords Permutation pattern · Permutation group · Intransitive group · Imprimitive group · Primitive group · Galois connection Mathematics Subject Classification 05A05 · 20B05
1 Introduction This study combines two different points of view to permutations: the algebraic one of permutation groups and the combinatorial one of permutation patterns. Permutation groups are a fundamental and extensively studied topic in classical algebra, and it requires no further introduction here. The theory of permutation patterns and pattern avoidance has been an active field of research over the past decades. The basic building block of the theory is the pattern involvement relation, which is a partial order on the set of all finite permutations (see Sect. 2 for precise definitions). Sets of permutations that are downwards closed with respect to the pattern involvement order are called permutation classes. Permutation classes can be equivalently described by certain pattern avoidance conditions. A recurrent theme in the theory of permutation patterns is that of describing and enumerating specific permutation classes, especially classes avoiding a small number of patterns. Following this line of research, we focus in this paper on permutation
B 1
Erkko Lehtonen [email protected] Technische Universität Dresden, Institut für Algebra, 01062 Dresden, Germany
123
Journal of Algebraic Combinatorics
classes that are motivated by algebraic considerations. Namely, there is a perhaps surprising connection between permutation patterns and permutation groups that was observed by Pöschel and the current author in [12]: for any permutation group G, a subgroup of the symmetric group S , and for every n ≥ , the set of n-permutations involving only members of G as -patterns is a subgroup of Sn ; in other words, the class Av(S \G) of permutations avoiding the complement of G is comprised of levels that are permutation groups. All this is closely related to the work of Atkinson and Beals [1,2] on group classes, that is, permutation classes in which every level is a permutation group. They determined how level sequences of group classes eventually behave (see Theorem 3.1). Moreover, they completely and explicitly described those group classes in which every level is a transitive group (see Theorem 3.2). The main goal of the current paper is, in other words, to refine and strengthen Atki
Data Loading...
