A New Notion of Transitivity for Groups and Sets of Permutations

Let = {1, 2, ..., n} where n 2. The shape of an ordered setpartition P = (P₁, ..., P_k) of is the integer partition =(₁, ..., _k) defined by _i = |P_i|. Let G be a group of permutationsacting on . For a fixed partition of n, we say that G is -transitiveif G has only one orbit when acting on partitions P of shape. A corresponding definition can also be given when G is justa set. For example, if = (n – t, 1, ..., 1), then a -transitivegroup is the same as a t-transitive permutation group, and if = (n – t, t), then we recover the t-homogeneous permutationgroups. We use the character theory of the symmetric group S_n to establishsome structural results regarding -transitive groups and sets.In particular, we are able to generalize a celebrated resultof Livingstone and Wagner [Math. Z. 90 (1965) 393–403]about t-homogeneous groups. We survey the relevant examplescoming from groups. While it is known that a finite group ofpermutations can be at most 5-transitive unless it containsthe alternating group, we show that it is possible to constructa nontrivial t-transitive set of permutations for each positiveinteger t. We also show how these ideas lead to a combinatorialbasis for the Bose–Mesner algebra of the association schemeof the symmetric group and a design system attached to thisassociation scheme.