Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Maximal cocliques in the generating graphs of the alternating and symmetric groups

  • Author(s): Kelsey, Veronica;
  • Roney-Dougal, Colva M.
  • et al.

Published Web Location

https://doi.org/10.5070/C62156879Creative Commons 'BY' version 4.0 license
Abstract

The generating graph $\Gamma(G)$ of a finite group $G$ has vertex set the non-identity elements of $G$, with two elements adjacent 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 $\mathrm{S}_n$ and $\mathrm{A}_n$ are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal in the case of $G = \mathrm{A}_n$ and $\mathrm{S}_n$, when $n$ is prime and ${n \neq \frac{q^d-1}{q-1}}$ for all prime powers $q$ and $d \geq 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.

Mathematics Subject Classifications: 20D06, 05C25, 20B35

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View