PARTITION ACTIONS OF SYMMETRIC GROUPS AND REGULAR BIPARTITE GRAPHS
Jonathan James · Bulletin of the London Mathematical Society · 2006
A base of an action of a group G on a set Ω is a subset B ⊆ Ω such that the pointwise stabiliser of B in G is the identity. We prove that if Ω is the set of partitions of [1, kl] into l subsets of size k, then the action of Skl on Ω has a base of size two if and only if k ⩾ 3 and l ⩾ max {k + 3, 8}. This result completes a classification of the primitive base 2 actions of the symmetric groups. During the proof we show that there exists a k-regular bipartite graph G on 2l vertices with no non-trivial automorphisms fixing the bipartite blocks if and only if k ⩾ 3 and l ⩾ max {k + 3, 8}. 2000 Mathematics Subject Classification 20B30 (primary), 05C25 (secondary).