PARTITION ACTIONS OF SYMMETRIC GROUPS AND REGULAR BIPARTITE GRAPHS

Abstract

A base of an action of a group G on a set $\Omega$ is a subset $B \subseteq \Omega$ such that the pointwise stabiliser of $B$ in $G$ is the identity. We prove that if $\Omega$ is the set of partitions of $[ 1, kl ]$ into $l$ subsets of size $k$, then the action of $S_{kl}$ on $\Omega$ has a base of size two if and only if $k \geq 3$ and $l \geq \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 $\mathcal{G}$ on $2l$ vertices with no non-trivial automorphisms fixing the bipartite blocks if and only if $k \geq 3$ and $l \geq \max \{ k + 3, 8 \}$.