Partition graphs for finite symmetric groups (Q4344211)

The authors investigate a class of arc-transitive graphs admitting a finite symmetric group \(S_n\) acting primitively on vertices. If \(S_n\) acts naturally on \(\Omega_n=\{1,2,\dots,n\}\), where \(n=mr\), then the vertex set of the resulting graph \(\Gamma\) can be viewed as the set of all partitions of \(\Omega_n\) into \(r\) subsets each of size \(m\), and the edges can be characterized by a matrix of order \(r\) whose row and column sums are all equal to \(m\). Several basic properties of these graphs are studied: the girth, the action of the stabilizer of a vertex \(x\) on the set of its neighbours, the action of the automorphism group on the set of 2-arcs. All partition graphs with the property that a vertex and each of its neighbours are stabilized by a non-identical automorphism are classified. This result is used to show that a 3-cycle is the only partition graph on which \(S_n\) acts 2-arc transitively. The interest in this class of graphs arose in the problem of classifying distance-transitive graphs with a finite alternating group or a symmetric group as automorphism group.