On the Saxl graph of a permutation group

Let $G$ be a permutation group on a set $\mathrm{\Omega }$. A subset of $\mathrm{\Omega }$ is a base for $G$ if its pointwise stabiliser in $G$ is trivial. In this paper we introduce and study an associated graph $\mathrm{\Sigma }(G)$, which we call the Saxl graph of $G$. The vertices of $\mathrm{\Sigma }(G)$ are the points of $\mathrm{\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 $\mathrm{\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 $\mathrm{\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.