Abstract :
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.
