On the Saxl graph of a permutation group

Abstract

Let $G$ be a permutation group on a set $\Omega$. A subset of $\Omega$ is a base for $G$ if its pointwise stabiliser in $G$ is trivial. In this paper we introduce and study an associated graph $\Sigma (G)$, which we call the Saxl graph of $G$. The vertices of $\Sigma (G)$ are the points of $\Omega$, and two vertices are adjacent if they form a base for $G$. This graph encodes some interesting properties of the permutation group. We investigate the connectivity of $\Sigma (G)$ for a finite transitive group $G$, as well as its diameter, Hamiltonicity, clique and independence numbers, and we present several open problems. For instance, we conjecture that if $G$ is a primitive group with a base of size $2$, then the diameter of $\Sigma (G)$ is at most $2$. Using a probabilistic approach, we establish the conjecture for some families of almost simple groups. For example, the conjecture holds when $G=S_n$ or $A_n$ (with $n>12$) and the point stabiliser of $G$ is a primitive subgroup. In contrast, we can construct imprimitive groups whose Saxl graph is disconnected with arbitrarily many connected components, or connected with arbitrarily large diameter.

27 pages; to appear in Math. Proc. Cambridge Philos. Soc

References in corpus (2)

• The base size of a primitive diagonal group
• Regular orbits of symmetric and alternating groups

Cited by in corpus (2)

• On Valency Problems of Saxl Graphs
• Base sizes for primitive groups with soluble stabilisers