Maximal Cocliques in the Generating Graphs of the Alternating and Symmetric Groups

Abstract

The generating graph $\Gamma (G)$ of a finite group $G$ has vertex set the non-identity elements of $G$, with two elements connected exactly when they generate $G$. A coclique in a graph is an empty induced subgraph, so a coclique in $\Gamma (G)$ is a subset of $G$ such that no pair of elements generate $G$. A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of $G$ form a coclique in $\Gamma (G)$, but this coclique need not be maximal. In this paper we determine when the intransitive maximal subgroups of ${\text{S}}_n$ and ${\text{A}}_n$ are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal [3] in the case of $G={\text{A}}_n$ and ${\text{S}}_n$, when n is prime and $n\ne \frac{(q^d-1)}{(q-1)}$ for all prime powers $q$ and $d\ge 2$. Namely, we show that two elements of $G$ have identical sets of neighbours in $\Gamma (G)$ if and only if they belong to exactly the same maximal subgroups.

Cited by in corpus (1)

• Coclique level structure for stochastic chemical reaction networks