A NEW NOTION OF TRANSITIVITY FOR GROUPS AND SETS OF PERMUTATIONS

Let Ω = {1, 2, . . . , n} where n 2. The shape of an ordered set partition P = (P1, . . . , Pk) of Ω is the integer partition λ = (λ1, . . . ,λk) defined by λi = |Pi|. Let G be a group of permutations acting on Ω. For a fixed partition λ of n, we say that G is λ-transitive if G has only one orbit when acting on partitions P of shape λ. A corresponding definition can also be given when G is just a set. For example, if λ = (n − t, 1, . . . , 1), then a λ-transitive group is the same as a t-transitive permutation group, and if λ = (n −t, t), then we recover the t-homogeneous permutation groups. We use the character theory of the symmetric group Sn to establish some structural results regarding λ-transitive groups and sets. In particular, we are able to generalize a celebrated result of Livingstone and Wagner [Math. Z. 90 (1965) 393–403] about t-homogeneous groups. We survey the relevant examples coming from groups. While it is known that a finite group of permutations can be at most 5-transitive unless it contains the alternating group, we show that it is possible to construct a nontrivial t-transitive set of permutations for each positive integer t. We also show how these ideas lead to a combinatorial basis for the Bose–Mesner algebra of the association scheme of the symmetric group and a design system attached to this association scheme.