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 = ( P 1 , …, P k ) of Ω is the integer partition λ = (λ 1 , …, λ k ) defined by λ i = | P i |. 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 S n 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.