Base Size and Saxl Graph

Base

Definition

Let $G$ be a transitive permutation group on a finite set $\Omega$. A base for $G$ is a subset of $\Omega$ with trivial pointwise stabilizer. The base size of $G$, denoted $b(G)$, is the minimal size of a base.

Saxl Graph

Definition

If $b(G)=2$ then we can study the Saxl graph $\Sigma (G)$ of $G$, which has vertex set $\Omega$ and two vertices are adjacent if and only if they form a base.

Lemma

Let $G⩽\mathrm{Sym}(\Omega )$ be a finite transitive permutation group with point stabiliser $H$. Suppose $b(G)=2$ and let $\Sigma (G)$ be the Saxl graph of $G$.

• $G⩽\mathrm{Aut}(\Sigma (G))$ acts transitively on the set of vertices of $\Sigma (G)$. In particular, $\Sigma (G)$ is a vertex-transitive graph with no isolated vertices.
• $\Sigma (G)$ is connected if $G$ is primitive.
• $\Sigma (G)$ is complete if and only if $G$ is Frobenius.
• $\Sigma (G)$ is arc-transitive if $G$ is 2-transitive, and edge-transitive if $G$ is 2-homogeneous.
• $\Sigma (G)$ has valency $r|H|$, where $r$ is the number of regular orbits of $H$ on $\Omega$.
• $\Sigma (G)$ is a subgraph of $\Sigma (K)$ for every subgroup $K$ of $G$.
• $G$ acts semi-regularly on the set of arcs of $\Sigma (G)$.
• If $G_{\alpha }=G_{\beta }$, then $\alpha$ and $\beta$ have the same set of neighbors in $\Sigma (G)$.

\begin{proof} i)-iv) are easy.

v) Since $\{\alpha ,\beta \}$ is a base for $G$ if and only if $G_{\alpha }$ acts regularly on ${\beta }^{G_{\alpha }}$, it follows that the set of neighbors of $\alpha$ in $\Sigma (G)$ is the union of the regular orbits of $G_{\alpha }$.

vi)-viii) are easy. \end{proof}

Remark. Fix a point $\alpha \in \Omega$. Recall that the orbits of $G$ on $\Omega \times \Omega$ are called orbitals and each orbital defines the set of arcs of an orbital digraph for $G$ with vertex set $\Omega$. For each orbital $\Delta$, the set $\Delta (\alpha )=\{\beta \in \Omega :(\alpha ,\beta )\in \Delta \}$ is an orbit of $G_{\alpha }$, which we call a suborbit of $G$. This gives a one-to-one correspondence between orbitals and suborbits. As noted in the proof of Lemma 2.1(v), the union of the regular orbits of $G_{\alpha }$ form the set of neighbours of $\alpha$ in $\Sigma (G)$. Each regular suborbit gives an orbital of size $|\Omega |\left|G_{\alpha }\right|$ and the arcs of $\Sigma (G)$ are the elements of these orbitals. In particular, $\Sigma (G)$ is the generalized orbital graph corresponding to the regular suborbits of $G$. This remark is copied here.

Proposition

For a primitive affine group $G=VH$ with $H⩽\mathrm{GL}(V)$ is irreducible, we get $b(G)=2$ if and only if $H$ has a regular orbit on $V$.

Generalized Saxl Graph

Definition

For a group $G$ with $b(G)⩾2$, we defined a generalized Saxl graph, whose edges are the pairs of elements of $\Omega$ that can be extended to bases of size $b(G)$.