# Vertex-primitive digraphs with large fixity

Marco Barbieri  Dipartimento di Matematica “Felice Casorati”, University of
Pavia, Via Ferrata 5, 27100 Pavia, Italy
<EMAIL_ADDRESS>and  Primož Potočnik  Faculty of
Mathematics and Physics, University of Ljubljana, Slovenia;
also affiliated with
Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia
<EMAIL_ADDRESS>
###### Abstract.

The relative fixity of a digraph $\Gamma$ is defined as the ratio between the
largest number of vertices fixed by a nontrivial automorphism of $\Gamma$ and
the number of vertices of $\Gamma$. We characterize the vertex-primitive
digraphs whose relative fixity is at least $\frac{1}{3}$, and we show that
there are only finitely many vertex-primitive graphs of bounded out-valency
and relative fixity exceeding a positive constant.

###### Key words and phrases:

Vertex-primitive, fixity, product action, digraph, graph

###### 2010 Mathematics Subject Classification:

05C25, 20B25

##  1\. Introduction

Throughout this paper, we use the word _digraph_ to denote a combinatorial
structure $\Gamma$ determined by a finite nonempty set of vertices $V\Gamma$
and a set of arcs $A\Gamma\subseteq V\Gamma\times V\Gamma$, sometimes also
viewed as a binary relation on $V\Gamma$. If the set $A\Gamma$ is symmetric
(when viewed as a binary relation on $V\Gamma$), then the digraph $\Gamma$ is
called a graph and unordered pairs $\\{u,v\\}$ such that $(u,v)$ and $(v,u)$
are arcs are called edges of $\Gamma$.

The fixity of a finite digraph $\Gamma$, denoted by ${\mathrm{Fix}}(\Gamma)$,
is defined as the largest number of vertices that are left fixed by a
nontrivial automorphism of $\Gamma$, while the relative fixity of $\Gamma$ is
defined as the ratio

${\mathrm{RelFix}}(\Gamma)=\frac{{\mathrm{Fix}}(\Gamma)}{|V\Gamma|}\,.$

The notion of fixity of (di)graphs was introduced in a 2014 paper of L. Babai
[2] (see also [4]), where several deep results regarding the fixity of
strongly regular graphs were proved (these results were later used in his work
on the graph isomorphism problem [3]). To convey the flavour of his work, let
us mention [4, Theorem 1.6], which states that the relative fixity of a
strongly regular graph (other then a complete bipartite graph or the line
graph of a complete graph) is at most $\frac{7}{8}$.

The study of the fixity of graphs continued in a series of papers [5, 19, 25]
by P. Spiga and coauthors (including the authors of the present paper), where
the problem was studied in the context of vertex-transitive graphs of fixed
valency.

Let us mention that fixity is a well studied parameter in the slightly more
general context of permutation groups, where, instead of fixity, it is more
common to consider the dual notion of minimal degree of a permutation group
$G$, defined by

$\mu(G)=\min_{g\in G\setminus\\{1_{G}\\}}|\mathrm{supp}(g)|\,,$

where $\mathrm{supp}(g)$ denotes the set of all non-fixed points of $g\in G$.
Note that the fixity of a digraph $\Gamma$ and the minimal degree of its
automorphism group ${\mathrm{Aut}}(\Gamma)$ are related via the equality

${\mathrm{Fix}}(\Gamma)=|V(\Gamma)|-\mu({\mathrm{Aut}}(\Gamma))\,.$

A vast majority of papers on the topic of minimal degree of permutation groups
(including the original work of Jordan on primitive permutation groups of
minimal degree $c$ for a fixed constant $c$) concentrates on primitive
permutation groups (see, for example, [1, 8, 13, 20, 23, 24]). It is thus
natural to ask the following question:

######  Question 1.

What can be said about a digraph with large relative fixity whose automorphism
group acts primitively on the vertex-set?

In this paper, we answer this question in the setting where the relative
fixity is more than $\frac{1}{3}$. In our analysis, we rely heavily on the
recent classification of primitive permutation groups of minimal degree at
most $\frac{2}{3}$ of the degree of the permutation group from [8]. The
essence of our work thus consists of determining the digraphs upon which the
permutation groups from this classification act upon.

Before stating our main result, let us first introduce a few graph theoretical
concepts and constructions. First, recall that the direct product of the
family of digraphs $\Gamma_{1},\ldots,\Gamma_{r}$ (sometimes also called the
tensor product or the categorical product) is the digraph
$\Gamma_{1}\times\ldots\times\Gamma_{r}$ whose vertex-set is the cartesian
product $V\Gamma_{1}\times\ldots\times V\Gamma_{r}$ and whose arc-set is

$A(\Gamma_{1}\times\ldots\times\Gamma_{r})=\left\\{\bigl{(}(u_{1},\ldots,u_{r}),\,(v_{1},\ldots,v_{r})\bigr{)}\,\middle|\,(u_{i},v_{i})\in
A\Gamma_{i}\hbox{ for all }i\in\\{1,\ldots,r\\}\right\\}\,.$

Recall also that a union of digraphs $\Gamma_{1}$ and $\Gamma_{2}$ is the
digraph whose vertex-set and arc-set are the sets $V\Gamma_{1}\cup
V\Gamma_{2}$ and $A\Gamma_{1}\cup A\Gamma_{2}$, respectively. Note that when
$\Gamma_{1}$ and $\Gamma_{2}$ share the same vertex-set, their union is then
obtained simply by taking the union of their arc-sets. Further, for a positive
integer $m$, let ${\mathbf{L}}_{m}$ and ${\mathbf{K}}_{m}$ denote the loop
graph and the complete graph on a vertex-set $V$ of cardinality $m$ and with
arc-sets $\\{(v,v):v\in V\\}$ and $\\{(u,v):u,v\in V,u\not=v\\}$,
respectively.

We now have all the ingredients needed to present a construction yielding the
digraph appearing in our main result.

######  Construction 2.

Let ${\mathcal{G}}=\\{\Gamma_{0},\Gamma_{1},\ldots,\Gamma_{k}\\}$ be a list of
$k+1$ pairwise distinct digraphs sharing the same vertex-set $\Delta$. Without
loss of generality, we shall always assume that $\Gamma_{0}={\mathbf{L}}_{m}$
with $m=|\Delta|$. Further, let $r$ be a positive integer, and let
${\mathcal{J}}$ be a subset of the $r$-fold cartesian power $X^{r}$, where
$X=\\{0,1,\ldots,k\\}$. Given this input, construct the digraph

${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})=\bigcup_{(j_{1},j_{2},\ldots,j_{r})\in{\mathcal{J}}}\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}$

and call it the merged product action digraph.

######  Remark 3.

We give some example to give a flavour of what can be obtained using
Construction 2.

If $r=1$, then ${\mathcal{P}}(1,{\mathcal{G}},{\mathcal{J}})$ is simply the
union of some digraphs from the set ${\mathcal{G}}$.

If $r=2$ and ${\mathcal{J}}=\\{(1,0),(0,1)\\}$, then
${\mathcal{P}}(1,{\mathcal{G}},{\mathcal{J}})={\mathbf{L}}_{m}\times\Gamma_{1}\cup\Gamma_{1}\times{\mathbf{L}}_{m}$,
which is, in fact, the Cartesian product $\Gamma\square\Gamma$. (This product
is sometimes called the box product, and we refer to [14] for the definition
of the Cartesian product.)

More generally, if ${\mathcal{J}}=\\{e_{i}\mid i\in\\{1,\ldots,r\\}\\}$, where
$e_{i}=(0,\ldots,0,1,0,\ldots,0)$ is the $r$-tuple with $1$ in the $i$-th
component and zeroes elsewhere, then
${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})=(\Gamma_{1})^{\square r}$, the
$r$-th Cartesian power of the graph $\Gamma_{1}\in{\mathcal{G}}$. More
specifically, if $\Gamma_{1}={\mathbf{K}}_{m}$ and ${\mathcal{J}}$ is as
above, then ${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$ is the Hamming
graph $\mathbf{H}(r,m)={\mathbf{K}}_{m}^{\square r}$.

While ${\mathcal{J}}$ can be an arbitrary set of $r$-tuples in $X^{r}$, we
will be mostly interested in the case where ${\mathcal{J}}\subseteq X^{r}$ is
invariant under the induced action of some permutation group
$H\leq{\mathrm{Sym}}(r)$ on the set $X^{r}$ given by the rule

$(j_{1},j_{2},\ldots,j_{r})^{h}=(j_{1h^{-1}},j_{2h^{-1}},\ldots,j_{rh^{-1}})\,.$

(Throughout this paper, in the indices, we choose to write $ih^{-1}$ instead
of $i^{h^{-1}}$ for improved legibility.) We shall say that ${\mathcal{J}}$ is
an $H$-invariant subset of $X^{r}$ in this case. A subset
${\mathcal{J}}\subseteq X^{r}$ which is $H$-invariant for some transitive
subgroup of ${\mathrm{Sym}}(r)$ will be called homogeneous.

The last example of Remark 3 justifies the introduction of the following new
family of graphs.

######  Definition 4.

Let $r,m$ be two positive integers, and let
${\mathcal{J}}\subseteq\\{0,1\\}^{r}$ be a homogeneous set. The graph
${\mathcal{P}}\left(r,\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m}\\},{\mathcal{J}}\right)$
is called _generalised Hamming graph_ and is denoted by
$\mathbf{H}(r,m,{\mathcal{J}})$.

######  Remark 5.

The generalised Hamming graphs $\mathbf{H}(r,m,{\mathcal{J}})$, where
${\mathcal{J}}$ is $H$-invariant, are precisely the unions of orbital graphs
for the group ${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}H$ endowed with the
product action (see Lemma 18 for further details).

Furthermore, a homogeneous set ${\mathcal{J}}$ is said to be _Hamming_ if,

${\mathcal{J}}=\bigcup\limits_{h\in H}\left((X\setminus\\{0\\})^{a}\times
X^{b}\times\\{0\\}^{r-a-b}\right)^{h}\,,$

for some nonnegative integers $a,b$ such that $a+b\leq r$ and a transitive
group $H\leq{\mathrm{Sym}}(r)$. It is said to be _non-Hamming_ otherwise.

######  Remark 6.

Let ${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$ be a merged product action
digraph, where the digraphs in ${\mathcal{G}}$ have $m$ vertices, and where
${\mathcal{J}}$ is a Hamming set. Build
${\mathcal{J}}^{\prime}\subseteq\\{0,1\\}^{r}$ from ${\mathcal{J}}$ by
substituting any nonzero entry of a sequence in ${\mathcal{J}}$ with $1$. Then

${\mathcal{P}}\left(r,{\mathcal{G}},{\mathcal{J}}\right)={\mathcal{P}}\left(r,\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m}\\},{\mathcal{J}}^{\prime}\right)\,.$

In particular, a generalised Hamming graph arises from Construction 2 if and
only if ${\mathcal{J}}$ is a Hamming set.

######  Remark 7.

The ordering of the Cartesian components in the definition of a Hamming set
does not matter: indeed, a permutation of the components corresponds to a
conjugation of the group $H$ in ${\mathrm{Sym}}(r)$, thus defining isomorphic
digraphs in Construction 2.

We are ready to state our main result.

######  Theorem 8.

Let $\Gamma$ be a finite vertex-primitive digraph with at least one arc. Then

${\mathrm{RelFix}}(\Gamma)>\frac{1}{3}$

if and only if one of the following occurs:

  1. $(i)$

$\Gamma$ is a generalised Hamming graph $\mathbf{H}(r,m,{\mathcal{J}})$, with
$m\geq 4$, and

${\mathrm{RelFix}}(\Gamma)=1-\frac{2}{m}\,;$

  2. $(ii)$

$\Gamma$ is a merged product action graph
${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$, where $r\geq 1$, where
${\mathcal{J}}$ is a non-Hamming subset of $X^{r}$ with
$X=\\{0,1,\ldots,|{\mathcal{G}}|-1\\}$, and where ${\mathcal{G}}$ is as in one
of the following:

    1. $(a)$

${\mathcal{G}}=\\{\mathbf{J}(m,k,i)\mid i\in\\{0,1,\ldots,k\\}\\}$ is the
family of distance-$i$ Johnson graphs, where $k,m$ are fixed integers such
that $k\geq 2$ and $m\geq 2k+2$ (see Section 4.2 for details), and

${\mathrm{RelFix}}(\Gamma)=1-\frac{2k(m-k)}{m(m-1)}\,;$

    2. $(b)$

${\mathcal{G}}=\\{\mathbf{QJ}(2m,m,i)\mid i\in\\{0,1,\ldots,\lfloor
m/2\rfloor\\}\\}$ is the family of squashed distance-$i$ Johnson graphs, where
$m$ is a fixed integer with $m\geq 4$ (see Section 4.3 for details), and

${\mathrm{RelFix}}(\Gamma)=\frac{1}{2}\left(1-\frac{1}{2m-1}\right)\,;$

    3. $(c)$

${\mathcal{G}}=\\{{\mathbf{L}}_{m},\Gamma_{1},\Gamma_{2}\\}$, where
$\Gamma_{1}$ is a strongly regular graph listed in Section 4.4, $\Gamma_{2}$
is its complement, and

${\mathrm{RelFix}}(\Gamma)={\mathrm{RelFix}}(\Gamma_{1})$

(the relative fixities are collected in Table 1).

######  Remark 9.

Although we do not assume that a vertex-primitive digraph $\Gamma$ in Theorem
8 is a graph, the assumption of large relative fixity forces it to be such. In
other words, every vertex-primtive digraph of relative fixity larger than
$\frac{1}{3}$ is a graph.

######  Remark 10.

The relative fixity can be arbitrarily close to $1$. Indeed, this can be
achieved by choosing a generalised Hamming graph
$\mathbf{H}(r,m,{\mathcal{J}})$ with $m$ arbitrarily large.

By analysing the vertex-primitive graphs of relative fixity more than
$\frac{1}{3}$, one can notice that the out-valency of these graphs must grow
as the number of vertices grows. More explicitly, a careful inspection of the
families in Theorem 8 leads to the following result, the proof of which we
leave out.

######  Remark 11.

There exists a constant $C$ such that every finite connected vertex-primitive
digraph $\Gamma$ with

${\mathrm{RelFix}}(\Gamma)>\frac{1}{3}$

satisfies

$\mathrm{val}(\Gamma)\geq C\log\left(|V\Gamma|\right)\,.$

Observe that, for the Hamming graphs $\mathbf{H}(r,m)$ with $m\geq 4$, we have
that

$\mathrm{val}\left(\mathbf{H}(r,m)\right)=r(m-1)\geq
r\log(m)=\log\left(|V\mathbf{H}(r,m)|\right)\,.$

In particular, as both expressions are linear in $r$, a logarithmic bound in
Remark 11 is the best that can be achieved.

One of the consequences of Remark 11 is that for every positive integer $d$
there exist only finitely many connected vertex-primitive digraphs of out-
valency at most $d$ and relative fixity exceeding $\frac{1}{3}$.

As Theorem 12 and Corollary 13 show, this remains to be true if $\frac{1}{3}$
is substituted by an arbitrary positive constant. We thank P. Spiga for
providing us with the main ideas used in the proof.

######  Theorem 12.

Let $\alpha$ and $\beta$ be two positive constants, and let $\mathcal{F}$ be a
family of quasiprimitive permutation groups $G$ on $\Omega$ satisfying:

  1. $(a)$

$\mu(G)\leq(1-\alpha)|\Omega|$; and

  2. $(b)$

$|G_{\omega}|\leq\beta$ for every $\omega\in\Omega$.

Then $\mathcal{F}$ is a finite family.

######  Corollary 13.

Let $\alpha$ be a positive constant, and let $d$ be a positive integer. There
are only finitely many vertex-primitive digraphs of out-valency at most $d$
and relative fixity exceeding $\alpha$.

The proof of Theorem 8 can be found in Section 5, while Theorem 12 and
Corollary 13 are proved in Section 6.

##  2\. Basic concepts and notations

###  2.1. Product action

We start by recalling the definition of a wreath product and its product
action. By doing so, we also settle the notation for the rest of the paper. We
refer to [12, Section 2.6 and 2.7] for further details.

Let $H$ be a permutation group on a finite set $\Omega$. Suppose that
$r=|\Omega|$, and, without loss of generality, identify $\Omega$ with the set
$\\{1,2,\ldots,r\\}$. For an arbitrary set $X$, we may define a permutation
action of $H$ of rank $r$ over $X$ as the the action of $H$ on the set $X^{r}$
given by the rule

$(x_{1},x_{2},\ldots,x_{r})^{h}=\left(x_{1h^{-1}},x_{2h^{-1}},\ldots,x_{rh^{-1}}\right)\,.$

Let $K$ be a permutation group on a set $\Delta$. We can consider the
permutation action of $H$ of rank $r$ over $K$ by letting

$(k_{1},k_{2},\ldots,k_{r})^{h}=(k_{1h^{-1}},k_{2h^{-1}},\ldots,k_{rh^{-1}})\quad\hbox{for
all }(k_{1},k_{2},\ldots,k_{r})\in K^{r},\,h\in H\,.$

If we denote by $\vartheta$ the homomorphism $H\to{\mathrm{Aut}}(K^{r})$
corresponding to this action, then the _wreath product of $K$ by $H$_, in
symbols $K\mathop{\mathrm{wr}}H$, is the semidirect product
$K^{r}\rtimes_{\vartheta}H$. We call $K^{r}$ the _base group_ , and $H$ the
_top group_ of this wreath product.

Note that the base and the top group are both embedded into
$K\mathop{\mathrm{wr}}H$ via the monomorphisms

$(k_{1},k_{2},\ldots,k_{r})\mapsto\left((k_{1},k_{2},\ldots,k_{r}),1_{H}\right)$

and

$h\mapsto\left((1_{K},1_{K},\ldots,1_{K}),h\right)\,.$

In this way, we may view the base and the top group as subgroups of the wreath
product and identify an element $((k_{1},k_{2},\ldots,k_{r}),h)\in
K\mathop{\mathrm{wr}}H$ with the product $(k_{1},k_{2},\ldots,k_{r})h$ of
$(k_{1},k_{2},\ldots,k_{r})\in K^{r}$ and $h\in H$ (both viewed as elements of
the group $K\mathop{\mathrm{wr}}H$).

The wreath product $K\mathop{\mathrm{wr}}H$ can be endowed with an action on
$\Delta^{r}$ by letting

$(\delta_{1},\delta_{2},\ldots,\delta_{r})^{(k_{1},k_{2},\ldots,k_{r})h}=\left(\delta_{1}^{k_{1}},\delta_{2}^{k_{2}},\ldots,\delta_{r}^{k_{r}}\right)^{h}=\left(\delta_{1h^{-1}}^{k_{1h^{-1}}},\delta_{2h^{-1}}^{k_{2h^{-1}}},\ldots,\delta_{rh^{-1}}^{k_{rh^{-1}}}\right)\,,$

for all
$(\delta_{1},\delta_{2},\ldots,\delta_{r})\in\Delta^{r},(k_{1},k_{2},\ldots,k_{r})\in
K^{r}$, and $h\in H$. We call this action the _product action of the wreath
product $K\mathop{\mathrm{wr}}H$ on $\Delta^{r}$_.

We recall the condition for a wreath product endowed with product action to be
primitive.

######  Lemma 14 ([12, Lemma 2.7A]).

Let $K$ be a permutation group on $\Delta$ and let $H$ be a permutation group
on $\Omega$. The wreath product $K\mathop{\mathrm{wr}}H$ endowed with the
product action on $\Delta^{r}$ is primitive if and only if $H$ is transitive
and $K$ is primitive but not regular.

We now introduce some notation to deal with any subgroup $G$ of
$\mathrm{Sym}(\Delta)\mathop{\mathrm{wr}}\mathrm{Sym}(\Omega)$ endowed with
product action on $\Delta^{r}$.

By abuse of notation, we identify the set $\Delta$ with

$\left\\{\\{\delta\\}\times\Delta^{r-1}\,\middle|\,\delta\in\Delta\right\\}$

via the mapping $\delta\mapsto\\{\delta\\}\times\Delta^{r-1}$. We denote by
$G_{\Delta}^{\Delta}$ the permutation group that $G_{\Delta}$ induces on
$\Delta$, that is,

$G_{\Delta}^{\Delta}\cong G_{\Delta}/G_{(\Delta)}\,.$

(Recall that $G_{(\Delta)}$ denotes the pointwise stabilizer of $\Delta$.)

Moreover, recalling that every element of $G$ can be written uniquely as $gh$,
for some $g\in{\mathrm{Sym}}(\Delta)^{r}$ and some
$h\in{\mathrm{Sym}}(\Omega)$, we can define the group homomorphism

$\psi:G\to{\mathrm{Sym}}(\Omega),\quad gh\mapsto h\,.$

This map defines a new permutational representation of $G$ acting on $\Omega$.
We denote by $G^{\Omega}$ the permutation group corresponding to the faithful
action that $G$ defines on $\Omega$, that is,

$G^{\Omega}\cong G/\ker(\psi)\,.$

Recall that a primitive group $G$, according to the O’Nan–Scott classification
(see, for instance, [22, III$(b)(i)$]), is said to be of _product action type_
if there exists a transitive group $H\leq{\mathrm{Sym}}(\Omega)$ and a
primitive almost simple group $K\leq{\mathrm{Sym}}(\Delta)$ with socle $T$
such that, for some integer $r\geq 2$,

$T^{r}\leq G\leq K\mathop{\mathrm{wr}}H\,,$

where $T^{r}$ is the socle of $G$, thus contained in the base group $K^{r}$. A
detailed description of primitive groups of product action type was given by
L. G. Kovács in [18].

######  Remark 15.

By [26, Theorem 1.1 $(b)$], a group $G$ of product action type is
permutationally isomorphic to a subgroup of
$G^{\Delta}_{\Delta}\mathop{\mathrm{wr}}G^{\Omega}$. Therefore, up to a
conjugation in ${\mathrm{Sym}}(\Delta^{r})$, the group $K$ can always be
chosen as $G^{\Delta}_{\Delta}$, and $H$ as $G^{\Omega}$.

###  2.2. Groups acting on digraphs

We give a short summary of standard notations for digraphs and graphs.

If a subgroup $G\leq\mathrm{Aut}(\Gamma)$ is primitive on $V\Gamma$, we say
that $\Gamma$ is _$G$ -vertex-primitive_. In a similar way, if $G$ is
transitive on $A\Gamma$, we say that $\Gamma$ is _$G$ -arc-transitive_. The
analogue notions can be defined for graphs, and when
$G={\mathrm{Aut}}(\Gamma)$ we drop the prefix $G$.

For any vertex $v\in{\mathrm{V}}\Gamma$, we denote by $\Gamma(v)$ its _out-
neighbourhood_ , that is, the set of vertices $u\in\Gamma$ such that $(v,u)\in
A\Gamma$. The size of the out-neighbourhood of a vertex $v$, $|\Gamma(v)|$, is
called _out-valency of $v$_. If $\Gamma$ is $G$-vertex-primitive, for some
group $G$, then the out-valency in independent of the choice of the vertex
$v$, thus we will refer to it as the _out-valency of $\Gamma$_, in symbols
$\mathrm{val}(\Gamma)$. Whenever $\Gamma$ is a graph, _neighbourhood_ and
_valency_ can be defined in the same way.

An _orbital for $G$_ is an orbit of $G$ in its induced action on
$\Omega\times\Omega$. An _orbital digraphs for $G$_ is a digraph whose vertex-
set is $\Omega$, and whose arc-set is an orbital for $G$. An example of
orbital for $G$ is the diagonal orbital $(\omega,\omega)^{G}$, whose
corresponding disconnected orbital graph is called diagonal orbital graph. We
refer to [12, Section 3.2] for further details.

Note that an orbital graph for $G$ is always $G$-arc-transitive, and,
conversely, every $G$-arc-transitive digraph is an orbital graph for $G$.
Furthermore, if $G\leq\mathrm{Aut}(\Gamma)$ is a group of automorphism for a
given digraph $\Gamma$, then $\Gamma$ is a union of orbitals for $G$ acting on
${\mathrm{V}}\Gamma$.

The number of distinct orbital digraphs for $G$ is called the _permutational
rank of $G$_. In particular, $2$-transitive permutation groups are precisely
those of permutational rank $2$.

If $A\subseteq\Omega\times\Omega$ is an orbital for $G$, then so is the set
$A^{*}=\\{(\beta,\alpha)\mid(\alpha,\beta)\in A\\}$. If $A=A^{*}$, then the
orbital $A$ is called self-paired. Similarly, an orbital digraph is self-
paired if its arc-set is a self-paired orbital. Note that any $G$-arc-
transitive graph is obtained from a self-paired orbital digraph for $G$.

##  3\. Orbital digraphs for wreath products in product action

We are interested in reconstructing the orbital digraphs of a wreath product
$K\mathop{\mathrm{wr}}H$ endowed with product action once the orbital digraphs
of $K$ are known.

######  Lemma 16.

Let $K\mathop{\mathrm{wr}}H$ be a wreath product endowed with the product
action on $\Delta^{r}$, and let

${\mathcal{G}}=\\{\Gamma_{0},\Gamma_{1},\ldots,\Gamma_{k}\\}$

be the complete list of the orbital digraphs for $K$. Then any orbital digraph
is a merged product action digraph of the form

${\mathcal{P}}\left(r,{\mathcal{G}},(j_{1},j_{2},\ldots,j_{r})^{H}\right)\,,$

for a sequence of indices $(j_{1},j_{2},\ldots,j_{r})\in X^{r}$, where
$X=\\{0,1,\ldots,k\\}$.

###### Proof.

Let $\Gamma$ be an orbital digraph for $K\mathop{\mathrm{wr}}H$. Suppose that
$(u,v)\in A\Gamma$, where $u=(u_{1},u_{2},\ldots,u_{r})$ and
$v=(v_{1},v_{2},\ldots,v_{r})$. We aim to compute the
$K\mathop{\mathrm{wr}}H$-orbit of $(u,v)$, and, in doing so, proving that
there is a sequence of indices $(j_{1},j_{2},\ldots,j_{r})\in X^{r}$ such that

$A\Gamma=A{\mathcal{P}}\left(r,{\mathcal{G}},(j_{1},j_{2},\ldots,j_{r})^{H}\right)\,.$

We start by computing the $K^{r}$-orbit of $(u,v)$ (where by $K^{r}$ we refer
to the base group of $K\mathop{\mathrm{wr}}H$). Since this action is
componentwise, we obtain that

$(u,v)^{K^{r}}=A\left(\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}\right)\,,$

where $(u_{i},v_{i})$ is an arc of $\Gamma_{j_{i}}$ for all $i=1,2,\ldots,r$.

The top group $H$ acts by permuting the components, so that

$(u,v)^{K\mathop{\mathrm{wr}}H}=\bigcup_{(j_{1}^{\prime},j_{2}^{\prime},\ldots,j_{r}^{\prime})\in(j_{1},j_{2},\ldots,j_{r})^{H}}A\left(\Gamma_{j_{1}^{\prime}}\times\Gamma_{j_{2}^{\prime}}\times\ldots\times\Gamma_{j_{r}^{\prime}}\right)$

Therefore, the arc-sets of $\Gamma$ and
${\mathcal{P}}\left(r,{\mathcal{G}},(j_{1},j_{2},\ldots,j_{r})^{H}\right)$
coincide.

As their vertex-sets are both $\Delta^{r}$, the proof is complete. ∎

Now that we know how to build the orbital digraphs for a permutation group in
product action, we ask ourselves what can we say about the orbital digraphs of
its subgroups.

######  Theorem 17.

Let $G\leq\mathrm{Sym}(\Delta)\mathop{\mathrm{wr}}\mathrm{Sym}(\Omega)$ be a
primitive group of product action type, and let $T$ be the socle of
$G_{\Delta}^{\Delta}$. Suppose that $T$ and $G_{\Delta}^{\Delta}$ share the
same orbital digraphs. Then the orbital digraphs for $G$ coincide with the
orbital digraphs for $G_{\Delta}^{\Delta}\mathop{\mathrm{wr}}G^{\Omega}$, or,
equivalently, for $T\mathop{\mathrm{wr}}G^{\Omega}$.

###### Proof.

Since $G$ is a primitive group of product action type, we can suppose that $G$
is a subgroup of $G_{\Delta}^{\Delta}\mathop{\mathrm{missing}}{wr}G^{\Omega}$
with socle $T^{r}$, where $r=|\Omega|$. Further, we set
$K=G_{\Delta}^{\Delta}$, $H=G^{\Omega}$.

As $G\leq K\mathop{\mathrm{wr}}H$, the partition of
$\Delta^{r}\times\Delta^{r}$ in arc-sets of orbital digraphs for
$K\mathop{\mathrm{wr}}H$ is coarser than the one for $G$. Hence, our aim is to
show that a generic orbital digraph for $K\mathop{\mathrm{wr}}H$ is also an
orbital digraph for $G$.

Let

${\mathcal{G}}=\\{\Gamma_{0},\Gamma_{1},\ldots,\Gamma_{k}\\}$

be the complete list of orbital digraphs for $T$ acting on $\Delta$, and let
$X=\\{0,1,\ldots,k\\}$. Observe that the set of orbital digraphs for $T^{r}$
can be identified with the Cartesian product of $r$ copies of ${\mathcal{G}}$:
indeed, we can bijectively map the generic orbital digraph $T^{r}$, say
$\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}$, for some
$(j_{1},j_{2},\ldots,j_{r})\in X^{r}$, to the generic $r$-tuple of the
Cartesian product ${\mathcal{G}}^{r}$ of the form
$(\Gamma_{j_{1}},\Gamma_{j_{2}},\ldots,\Gamma_{j_{r}})$. This point of view
explains why $H$ can act on the set of orbital digraphs for $T^{r}$ with its
action of rank $r$.

Observe that the set of orbital digraphs for $T^{r}$ is equal to the set of
orbital digraphs for $K^{r}$. Moreover, $T^{r}$ is a subgroup of $G$, and
$K^{r}$ is a subgroup of $K\mathop{\mathrm{wr}}H$. Thus the orbital digraphs
for $G$ and for $K\mathop{\mathrm{wr}}H$ are obtained as a suitable unions of
the elements of ${\mathcal{G}}^{r}$.

By Lemma 16, the orbital digraphs for $K\mathop{\mathrm{wr}}H$ are of the form

$\bigcup_{(j_{1}^{\prime},j_{2}^{\prime},\ldots,j_{r}^{\prime})\in(j_{1},j_{2},\ldots,j_{r})^{H}}\Gamma_{j_{1}^{\prime}}\times\Gamma_{j_{2}^{\prime}}\times\ldots\times\Gamma_{j_{r}^{\prime}}\,,$

for some $(j_{1},j_{2},\ldots,j_{r})\in X^{r}$. Aiming for a contradiction,
suppose that

$\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}\quad\hbox{and}\quad\Gamma_{i_{1}}\times\Gamma_{i_{2}}\times\ldots\times\Gamma_{i_{r}}$

are two distinct orbital digraphs for $T^{r}$ that are merged under the action
of top group $H$, but they are not under the action of $G$. The first portion
of the assumption yields that there is an element $h\in H$ such that

$\left(\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}\right)^{h}=\Gamma_{i_{1}}\times\Gamma_{i_{2}}\times\ldots\times\Gamma_{i_{r}}\,.$

By definition of $H=G^{\Omega}$, there is an element in $G$ of the form

$(g_{1},g_{2},\ldots,g_{r})h\in G.$

Recalling that, for any $i=1,2,\ldots,r$, $g_{i}\in K$, we get

$\left(\Gamma_{j_{1}}\times\Gamma_{j_{2}}\times\ldots\times\Gamma_{j_{r}}\right)^{(g_{1},g_{2},\ldots,g_{r})h}=\Gamma_{i_{1}}\times\Gamma_{i_{2}}\times\ldots\times\Gamma_{i_{r}}\,.$

Therefore, the merging among these orbital graphs is also realised under the
action of $G$, a contradiction.

By the initial remark, the proof is complete. ∎

##  4\. Daily specials

The aim of this section is to give a descriptions of the digraphs appearing in
Theorem 8.

###  4.1. Generalised Hamming graphs

In this section, we clarify Remark 5 and we compute the relative fixity of the
generalised Hamming graphs.

######  Lemma 18.

Let $H\leq{\mathrm{Sym}}(r)$ be a transitive permutation group, let
$G={\mathrm{Alt}}(\Delta)\mathop{\mathrm{wr}}H$ endowed with the product
action on $\Delta^{r}$, and let $\Gamma$ be a digraph with vertex-set
$V\Gamma=\Delta^{r}$. Then $G\leq{\mathrm{Aut}}(\Gamma)$ if and only if
$\Gamma$ is a generalised Hamming graph $\mathbf{H}(r,m,{\mathcal{J}})$, where
$|\Delta|=m$ and ${\mathcal{J}}\subseteq\\{0,1\\}^{r}$ is $H$-invariant.

###### Proof.

By applying Lemma 16 and taking the union of the resulting orbital digraphs,
we obtain the left-to-right direction of the equivalence. Let us now deal with
the converse implication. Let $\Gamma=\mathbf{H}(r,m,{\mathcal{J}})$, where
$|\Delta|=m$ and ${\mathcal{J}}\subseteq\\{0,1\\}^{r}$ is $H$-invariant. By
Construction 2 and Definition 4,

$\mathbf{H}(r,m,{\mathcal{J}})=\bigcup\limits_{h\in
H}\left(\bigcup\limits_{i=0}^{b}{\mathbf{K}}_{m}^{a+i}\times{\mathbf{L}}_{m}^{b+c-i}\right)^{h}\,,$

for some non negative integers $a,b$ such that $a+b\leq r$. As each component
of the graphs in parenthesis is either ${\mathbf{K}}_{m},{\mathbf{L}}_{m}$ or
${\mathbf{K}}_{m}\cup{\mathbf{L}}_{m}$, we have that

${\mathrm{Alt}}(m)^{r}\leq{\mathrm{Aut}}\left(\bigcup\limits_{i=0}^{b}{\mathbf{K}}_{m}^{a+i}\times{\mathbf{L}}_{m}^{b+c-i}\right)\,.$

Moreover, as ${\mathcal{J}}$ is $H$-invariant, the action of rank $r$ that $H$
induces on $\Delta^{r}$ preserves the arc-set of
$\mathbf{H}(r,m,{\mathcal{J}})$. As $G$ is generated by
${\mathrm{Alt}}(m)^{r}$ and this $H$ in their actions on $\Delta^{r}$, this
implies that $G\leq{\mathrm{Aut}}(\Gamma)$, as claimed. ∎

Instead of directly computing the relative fixity of
$\mathbf{H}(r,m,{\mathcal{J}})$, we prove the following stronger result.

######  Lemma 19.

Let $K\mathop{\mathrm{wr}}H$ be a wreath product endowed with the product
action on $\Delta^{r}$, and let $\Gamma$ be a digraph with vertex set
$\Delta^{r}$. Suppose that $K\mathop{\mathrm{wr}}H\leq{\mathrm{Aut}}(\Gamma)$.
Then

${\mathrm{RelFix}}(\Gamma)=1-\frac{\mu\left({\mathrm{Aut}}(\Gamma)\cap{\mathrm{Sym}}(\Delta)^{r}\right)}{|V\Gamma|}\,.$

In particular, the relative fixity of a generalised Hamming graph is

${\mathrm{RelFix}}\left(\mathbf{H}(r,m,{\mathcal{J}})\right)=1-\frac{2}{m}\,.$

###### Proof.

Suppose that $|\Delta|=m$, then, by hypothesis,

$K\mathop{\mathrm{wr}}H\leq{\mathrm{Aut}}(\Gamma)\leq{\mathrm{Sym}}(m)\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)\,.$

We claim that the automorphism that realizes the minimal degree must be
contained in ${\mathrm{Aut}}(\Gamma)\cap{\mathrm{Sym}}(m)^{r}$ (where
${\mathrm{Sym}}(m)^{r}$ is the base group of
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$). Indeed, upon
choosing an element of minimal degree in
$K\times\\{{\mathrm{id}}\\}\times\ldots\\{{\mathrm{id}}\\}$ and a
transposition from the top group in
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$, we obtain the
inequalities

$\begin{split}\mu\left({\mathrm{Aut}}(\Gamma)\cap{\mathrm{Sym}}(m)^{r}\right)&\leq\mu(K)m^{r-1}\\\
&\leq(m-1)m^{r-1}\\\ &\leq\min\left\\{|\mathrm{supp}(g)|\mid
g\in{\mathrm{Aut}}(\Gamma)\setminus{\mathrm{Sym}}(m)^{r}\right\\}\end{split}$

This is enough to prove the first portion of the statement.

In particular, to compute the relative fixity of
$\mathbf{H}(r,m,{\mathcal{J}})$, it is enough to look at the action of
${\mathrm{Sym}}(m)$ on a single component. Thus, upon choosing a transposition
in
${\mathrm{Sym}}(m)\times\\{{\mathrm{id}}\\}\times\ldots\\{{\mathrm{id}}\\}$,
we obtain

${\mathrm{RelFix}}\left(\mathbf{H}(r,m,{\mathcal{J}})\right)=1-\frac{2m^{r-1}}{m^{r}}=1-\frac{2}{m}\,.\qed$

###  4.2. Distance-$i$ Johnson graphs

The nomenclature dealing with possible generalizations of the Johnson graph is
as lush as confusing. In this paper, we are adopting the one from [16].

Let $m,k,i$ be integers such that $m\geq 1$, $1\leq k\leq m$ and $0\leq i\leq
k$. A _distance- $i$ Johnson graph_, denoted by $\mathbf{J}(m,k,i)$ is a graph
whose vertex-set is the family of $k$-subsets of $\\{1,2,\ldots,m\\}$, and
such that two $k$-subsets, say $X$ and $Y$, are adjacent whenever $|X\cap
Y|=k-i$. The usual Johnson graph is then $\mathbf{J}(m,k,1)$, and two subsets
$X$ and $Y$ are adjacent in $\mathbf{J}(m,k,i)$ if and only if they are at
distance-$i$ in $\mathbf{J}(m,k,1)$.

######  Lemma 20.

Let $m,k$ be two positive integers such that $m\geq 2k+2$. The orbital
digraphs of ${\mathrm{Alt}}(m)$ and of ${\mathrm{Sym}}(m)$ in their action on
$k$-subsets are the distance-$i$ Johnson graphs $\mathbf{J}(m,k,i)$, one for
each choice of $i\in\\{0,1,\ldots,k\\}$.

###### Proof.

Suppose that two $k$-subsets $X$ and $Y$ are such that $(X,Y)$ is an arc of
the considered orbital digraph and $|X\cap Y|=k-i$, for a nonnegative integer
$i\leq k$. Since ${\mathrm{Alt}}(m)$ is $(m-2)$-transitive and $2k\leq m-2$,
the ${\mathrm{Alt}}(m)$-orbit of the arc $(X,Y)$ contains all the pairs
$(Z,W)$, where $Z$ and $W$ are $k$-subsets with $|Z\cap W|=k-i$. Therefore,
the statement is true for the alternating group. The same proof can be
repeated _verbatim_ for ${\mathrm{Sym}}(m)$. ∎

######  Lemma 21.

Let $m,k,i$ be three positive integers such that $m\geq 2k+2$ and $i\neq k$.
Then the relative fixity of the distance-$i$ Johnson graphs
$\mathbf{J}(m,k,i)$ is

${\mathrm{RelFix}}(\mathbf{J}(m,k,i))=1-\frac{2k(m-k)}{m(m-1)}\,.$

###### Proof.

Under our assumption, by [15, Theorem 2 $(a)$], the automorphism group of
$\mathbf{J}(m,k,i)$ is ${\mathrm{Sym}}(m)$ in its action on $k$ subsets. Its
minimal degree is achieved by any transposition (see [13, Section 1]), where

$\mu\left({\mathrm{Sym}}(m)\right)=2\binom{m-2}{k-1}\,.$

Hence, we find that

${\mathrm{RelFix}}(\mathbf{J}(m,k,i))=1-\frac{2k(m-k)}{m(m-1)}\,.\qed$

###  4.3. Squashed distance-$i$ Johnson graphs

A usual construction in the realm of distance transitive graphs consist in
obtaining smaller example starting from a distance transitive graph and
identifying vertices at maximal distance. We need to apply this idea to a
family of generalised Johnson graphs.

Consider the distance-$i$ Johnson graph $\mathbf{J}(2m,m,i)$, for some
integers $m$ and $i$, with $m$ positive and $0\leq i\leq m$. We say that two
vertices of ${\mathbf{J}}(2m,m,i)$ are _disjoint_ if they have empty
intersection as $m$-subset. Observe that being disjoint is an equivalence
relation, and our definition coincides with the usual notion of antipodal for
${\mathbf{J}}(2m,m,1)$ seen as a metric space. We can build a new graph
$\mathbf{QJ}(2m,m,i)$ whose vertex-set is the set of equivalence classes of
the disjoint relation, and such that, if $[X]$ and $[Y]$ are two generic
vertices, then $([X],[Y])$ is an arc in $\mathbf{QJ}(2m,m,i)$ whenever there
is a pair of representatives, say $X^{\prime}\in[X]$ and $Y^{\prime}\in[Y]$,
such that $(X^{\prime},Y^{\prime})$ is an arc in ${\mathbf{J}}(2m,m,i)$. We
call $\mathbf{QJ}(2m,m,i)$ an _squashed distance- $i$ Johnson graph_.

Observe that $\mathbf{J}(2m,m,i)$ is a regular double cover of
$\mathbf{QJ}(2m,m,i)$. Furthermore, $\mathbf{QJ}(2m,m,i)$ and
$\mathbf{QJ}(2m,m,m-i)$ are isomorphic graphs, thus we can restrict the range
of $i$ to $\\{0,1,\ldots,\lfloor m/2\rfloor\\}$.

######  Lemma 22.

Let $m\geq 3$ be an integer. The orbital digraphs of ${\mathrm{Alt}}(2m)$ and
of ${\mathrm{Sym}}(2m)$ in their primitive actions with stabilizer
$({\mathrm{Sym}}(m)\mathop{\mathrm{wr}}C_{2})\cap{\mathrm{Alt}}(2m)$ and
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}C_{2}$ respectively are the squashed
distance-$i$ Johnson graphs $\mathbf{J}(m,k,i)$, one for each choice of
$i\in\\{0,1,\ldots,\lfloor m/2\rfloor\\}$.

###### Proof.

To start, we note that the set $\Omega$ on which the groups are acting can be
identified with the set of partitions of the set $\\{1,2,\ldots,2m\\}$ with
two parts of equal size $m$. Suppose that $\\{X_{1},X_{2}\\}$ and
$\\{Y_{1},Y_{2}\\}$ are two such partitions and that
$\left(\\{X_{1},X_{2}\\},\\{Y_{1},Y_{2}\\}\right)$ is an arc of the orbital
digraph we are building, with

$\min\\{|X_{1}\cap Y_{1}|,\,|X_{1}\cap Y_{2}|\\}=m-i\,,$

for a nonnegative integer $i\leq\lfloor m/2\rfloor$. To determine the image of
$\left(\\{X_{1},X_{2}\\},\\{Y_{1},Y_{2}\\}\right)$ under the group action, it
is enough to know the images of $X_{1}$ and $Y_{2}$, that is, of at most
$2m-\lceil m/2\rceil\leq 2m-2$ distinct points. By the $(2m-2)$-transitivity
of ${\mathrm{Alt}}(2m)$, the ${\mathrm{Alt}}(2m)$-orbit of
$\left(\\{X_{1},X_{2}\\},\\{Y_{1},Y_{2}\\}\right)$ contains all the arc of the
form $\left(\\{Z_{1},Z_{2}\\},\\{W_{1},W_{2}\\}\right)$, where
$\\{Z_{1},Z_{2}\\},\\{W_{1},W_{2}\\}\in\Omega$ and

$\min\\{|Z_{1}\cap W_{1}|,\,|Z_{1}\cap W_{2}|\\}=m-i\,.$

To conclude, observe that $\Omega$ is the set of $m$-subsets of
$\\{1,2,\ldots,2m\\}$ in which two elements are identified if they are
disjoint, and that

$\min\\{|X_{1}\cap Y_{1}|,\,|X_{1}\cap Y_{2}|\\}=m-i\,,$

is the adjacency condition in an squashed distance-$i$ Johnson graph. As in
Lemma 20, the same reasoning can be exteneded to ${\mathrm{Sym}}(2m)$.
Therefore, the orbital digraphs of ${\mathrm{Alt}}(2m)$ and of
${\mathrm{Sym}}(2m)$ in these primitive actions are the squashed distance-$i$
Johnson graphs $\mathbf{QJ}(2m,m,i)$, for some $i\in\\{0,1,\ldots,\lfloor
m/2\rfloor\\}$. ∎

######  Lemma 23.

Let $m,i$ be two positive integers such that $m\geq 3$ and $i\neq\lfloor
m/2\rfloor$. Then the relative fixity of the distance-$i$ Johnson graphs
$\mathbf{QJ}(2m,m,i)$ is

${\mathrm{RelFix}}(\mathbf{QJ}(2m,m,i))=1-\frac{2k(m-k)}{m(m-1)}\,.$

###### Proof.

Consider $\mathbf{J}(2m,m,i)$, the regular double covering of
$\mathbf{QJ}(2m,m,i)$. In view of [15, Theorem 2 $(e)$], the automorphism
group of $\mathbf{J}(2m,m,i)$ is ${\mathrm{Sym}}(2m)\times{\mathrm{Sym}}(2)$,
where the central involution swaps pairs disjoint vertices. It follows that
the automorphism group of $\mathbf{QJ}(2m,m,i)$ is ${\mathrm{Sym}}(2m)$. Now,
we can immediately verify that the stabilizer of the vertex
$\\{\\{1,2,\ldots,m\\},\\{m+1,m+2,\ldots,2m\\}\\}$ is
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}C_{2}$. The minimal degree of the
primitive action of ${\mathrm{Sym}}(2m)$ with stabilizer
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}C_{2}$ is

$\mu\left({\mathrm{Sym}}(2m)\right)=\frac{1}{4}\left(1+\frac{1}{2m-1}\right)\frac{(2m)!}{m!^{2}}$

(see [8, Theorem 4]). Thus, we find that

${\mathrm{RelFix}}(\mathbf{QJ}(2m,m,i))=\frac{1}{2}\left(1-\frac{1}{2m-1}\right)\,.\qed$

###  4.4. Strongly regular graphs

We list all the strongly regular graphs appearing as $\Gamma_{1}$ in Theorem 8
$(c)$. We divide them according to the socle $L$ of the almost simple group
that acts on them. Further, the present enumeration corresponds to the one of
the groups that act on these graphs as listed in (the soon to be enunciated)
Theorem 24 $(e)$.

  1. $(i)$

$L=U_{4}(q)$, $q\in\\{2,3\\}$, acting on totally singular $2$-dimensional
subspaces of the natural module, two vertices of $\Gamma$ are adjacent if
there is a third $2$-dimensional subspace that intersect both vertices in a
$1$-dimensional subspace (see [7, Section 2.2.12]);

  2. $(ii)$

$L=\Omega_{2m+1}(3),m\geq 2$, acting on the singular points of the natural
module, two vertices of $\Gamma$ are adjacent if they are orthogonal (see [7,
Theorem 2.2.12]);

  3. $(iii)$

$L=\Omega_{2m+1}(3),m\geq 2$, acting on the nonsingular points of the natural
module, two vertices of $\Gamma$ are adjacent if the line that connects them
is tangent to the quadric where the quadratic form vanishes (see [7, Section
3.1.4]);

  4. $(iv)$

$L=\mathrm{P}\Omega_{2m}^{\varepsilon}(2),\varepsilon\in\\{+,-\\},m\geq 3$,
acting on the singular points of the natural module, two vertices of $\Gamma$
are adjacent if they are orthogonal (see [7, Theorem 2.2.12]);

  5. $(v)$

$L=\mathrm{P}\Omega_{2m}^{\varepsilon}(2),\varepsilon\in\\{+,-\\},m\geq 2$,
acting on the nonsingular points of the natural module, two vertices of
$\Gamma$ are adjacent if they are orthogonal (see [7, Section 3.1.2]);

  6. $(vi)$

$L=\mathrm{P}\Omega_{2m}^{+}(3),m\geq 2$ acting on the nonsingular points of
the natural module, two vertices of $\Gamma$ are adjacent if they are
orthogonal (see [7, Section 3.1.3]);

  7. $(vii)$

$L=\mathrm{P}\Omega_{2m}^{-}(3),m\geq 3$ acting on the singular points of the
natural module, two vertices of $\Gamma$ are adjacent if they are orthogonal
(see [7, Theorem 2.2.12]);

  8. $(viii)$

$L=\mathrm{P}\Omega_{2m}^{-}(3),m\geq 2$ acting on the nonsingular points of
the natural module, two vertices of $\Gamma$ are adjacent if they are
orthogonal (see [7, Section 3.1.3]).

Table 1 collects the usual parameters of a strongly regular graph,
$(v,d,\lambda,\mu)$, and their relative fixity. Recall that $v$ is the number
of vertices, $d$ is the valency of the graph, $\lambda$ is the number of
common neighbours between two adjacent vertices, and $\mu$ is the number of
common neighbours between two nonadjacent vertices. As $\mu(G)$ can be found
in [8, Theorem 4], the relative fixity is computed as

${\mathrm{RelFix}}(\Gamma)=1-\frac{\mu(G)}{v}\,,$

| Socle | $v$ | $d$ | $\lambda$ | $\mu$ | ${\mathrm{RelFix}}$ | Comments
---|---|---|---|---|---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $(i)$ | $U_{4}(2)$ | $27$ | $10$ | $1$ | $5$ | $\dfrac{7}{27}$ |
| $U_{4}(3)$ | $112$ | $30$ | $2$ | $10$ | $\dfrac{11}{56}$ |
$\dfrac{1^{1}}{1_{1_{1}}}$ $(ii)$ | $\Omega_{2m+1}(3)$ | $\dfrac{1}{2}(9a-1)$ | $\dfrac{3}{2}(a^{2}-1)$ | $\dfrac{1}{2}(a^{2}-9)+2$ | $\dfrac{1}{2}(a^{2}-1)$ | $\dfrac{a+1}{3a+1}$ | $a=3^{m-1}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $(iii)$ | $\Omega_{2m+1}(3)$ | $\dfrac{3a}{2}(3a-1)$ | $(a-1)(3a+1)$ | $2(a^{2}-a-1)$ | $2a(a-1)$ | $\dfrac{3a^{2}+a+1}{3a(3a-1)}$ |
$\dfrac{1^{1}}{1_{1_{1}}}$ $(iv)$ | $\mathrm{P}\Omega_{2m}^{+}(2)$ | $(4b-1)(2b-1)$ | $2(2b-1)(b+1)$ | $(2b-2)(b-2)+1$ | $(2b-1)(b+1)$ | $\dfrac{b-1}{2b-1}$ | $b=2^{m-2}$
| $\mathrm{P}\Omega_{2m}^{-}(2)$ | $4b^{2}-1$ | $2(b^{2}-1)$ | $b^{2}-3$ | $b^{2}-1$ | $\dfrac{2b+1}{4b+1}$ |
$\dfrac{1^{1}}{1_{1_{1}}}$ $(v)$ | $\mathrm{P}\Omega_{2m}^{\varepsilon}(2)$ | $2b(4b-\varepsilon)$ | $4b^{2}-1$ | $2(b^{2}-1)$ | $b(2b+\varepsilon)$ | $\dfrac{2b}{4b-\varepsilon}$ | $\varepsilon=\pm 1$
$\dfrac{1^{1}}{1_{1_{1}}}$ $(vi)$ | $\mathrm{P}\Omega_{2m}^{+}(3)$ | $\dfrac{3c}{2}(9c-1)$ | $\dfrac{3c}{2}(3c-1)$ | $\dfrac{c}{2}(3c-1)$ | $\dfrac{3c}{2}(c-1)$ | $\dfrac{3(c+1)}{9c-1}$ | $c=3^{m-2}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $(vii)$ | $\mathrm{P}\Omega_{2m}^{-}(3)$ | $\dfrac{1}{2}(9c^{2}-1)$ | $\dfrac{3}{2}(c^{2}-1)$ | $\dfrac{1}{2}(c^{2}-9)+2$ | $\dfrac{1}{2}(c^{2}-1)$ | $\dfrac{3c+1}{9c+1}$ |
$\dfrac{1^{1}}{1_{1_{1}}}$ $(viii)$ | $\mathrm{P}\Omega_{2m}^{-}(3)$ | $\dfrac{3c}{2}(9c+1)$ | $\dfrac{3c}{2}(3c+1)$ | $\dfrac{c}{2}(3c-1)$ | $\dfrac{3c}{2}(c+1)$ | $\dfrac{9c^{2}+3c-2}{3c(9c+1)}$ |
Table 1. Parameters of strongly regular graphs with large fixity.

##  5\. Proof of Theorem 8

The primitive permutation groups we are concerned with were classified by T.
Burness and R. Guralnick in [8]. We report their result here. For the sake of
our proof, we explicitly write the permutational rank of the almost simple
groups of Lie type. This information can be easily obtained combining the
complete list of $2$-transitive finite permutation groups, first described by
P. J. Cameron in [9, Section 5], and the complete list of classical finite
permutation groups of permutational rank $3$, compiled by W. M. Kantor and R.
A. Liebler in [17, Theorem 1.1].

######  Theorem 24 ([8], Theorem 4).

Let $G$ be a permutation group with

$\mu(G)<\frac{2n}{3}\,.$

Then one of the following holds:

  1. $(a)$

${\mathrm{Alt}}(m)\leq G\leq{\mathrm{Sym}}(m)$, for some $m\geq 3$, in its
action on $k$-subsets, for some $k<m/2$;

  2. $(b)$

$G={\mathrm{Sym}}(2m)$, for some $m\geq 2$, in its primitive action with
stabilizer $G_{\alpha}={\mathrm{Sym}}(m)\mathop{\mathrm{wr}}C_{2}$;

  3. $(c)$

$G=M_{22}:2$ in its primitive action of degree $22$ with stabilizer
$G_{\alpha}=\mathrm{L}_{3}(4).2_{2}$;

  4. $(d)$

$G$ is an almost simple group of socle $L$ and permutational rank $2$, and one
of the following occurs:

    1. $(i)$

$L=\mathrm{L}_{m}(2)$, $m\geq 3$, in its natural action;

    2. $(ii)$

$L=\mathrm{L}_{m}(3)$, $m\geq 3$, in its natural action, and $G$ contains an
element of the form $(-I_{n-1},I_{1})$;

    3. $(iii)$

$L=\mathrm{Sp}_{2m}(2)$, $m\geq 3$, in its action on the singular points of
the natural module;

    4. $(iv)$

$L=\mathrm{Sp}_{2m}(2)$, $m\geq 3$, in its action on the right cosets of
${\mathrm{SO}^{-}_{2m}}(2)$;

    5. $(v)$

$L=\mathrm{Sp}_{2m}(2)$, $m\geq 3$, in its action on the right cosets of
${\mathrm{SO}^{+}_{2m}}(2)$;

  5. $(e)$

$G$ is an almost simple group of socle $L$ and permutational rank $3$, and one
of the following occurs:

    1. $(i)$

$L=U_{4}(q)$, $q\in\\{2,3\\}$, in its primitive action on totally singular
$2$-dimensional subspaces, and $G$ contains the graph automorphism $\tau$;

    2. $(ii)$

$L=\Omega_{2m+1}(3)$ in its action on the singular points of the natural
module, and $G$ contains an element of the form $(-I_{2m},I_{1})$ with a
$+$-type $(-1)$-eigenspace;

    3. $(iii)$

$L=\Omega_{2m+1}(3)$ in its action on the nonsingular points of the natural
module whose orthogonal complement is an orthogonal space of $-$-type, and $G$
contains an element of the form $(-I_{2m},I_{1})$ with a $-$-type
$(-1)$-eigenspace;

    4. $(iv)$

$L=\mathrm{P}\Omega_{2m}^{\varepsilon}(2)$, $\varepsilon\in\\{+,-\\}$, in its
action on the singular points on the natural module, and
$G=\mathrm{SO}_{2m}^{\varepsilon}(2)$;

    5. $(v)$

$L=\mathrm{P}\Omega_{2m}^{\varepsilon}(2)$, $\varepsilon\in\\{+,-\\}$, in its
action on the nonsingular points on the natural module, and
$G=\mathrm{SO}_{2m}^{\varepsilon}(2)$;

    6. $(vi)$

$L=\mathrm{P}\Omega_{2m}^{+}(3)$ in its action on the nonsingular points on
the natural module, and $G$ contains an element of the form
$(-I_{2m-1},I_{1})$ such that the discriminant of the $1$-dimensional
$1$-eigenspace is a nonsquare;

    7. $(vii)$

$L=\mathrm{P}\Omega_{2m}^{-}(3)$ in its action on the singular points on the
natural module, and $G$ contains an element of the form $(-I_{2m-1},I_{1})$;

    8. $(viii)$

$L=\mathrm{P}\Omega_{2m}^{-}(3)$ in its action on the nonsingular points on
the natural module, and $G$ contains an element of the form
$(-I_{2m-1},I_{1})$ such that the discriminant of the $1$-dimensional
$1$-eigenspace is a square;

  6. $(f)$

$G\leq K\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$ is a primitive group of product
action type, where $K$ is a permutation group appearing in points $(a)-(e)$,
the wreath product is endowed with the product action, and $r\geq 2$;

  7. $(g)$

$G$ is an affine group with a regular normal socle $N$, which is an elementary
abelian $2$-subgroup.

###### Proof of Theorem 8.

The proof is split in two independent chunks. First, we prove that every
vertex-primitive digraph of relative fixity exceeding $\frac{1}{3}$ belongs to
one of the families appearing in Theorem 8. Then, we tackle the problem of
computing the relative fixities of the graphs appearing in Theorem 8, thus
showing that they indeed all have relative fixity larger than $\frac{1}{3}$.

Assume that $\Gamma$ is a digraph on $n$ vertices with at least one arc and
with ${\mathrm{RelFix}}(\Gamma)>\frac{1}{3}$ such that
$G={\mathrm{Aut}}(\Gamma)$ is primitive. If $\Gamma$ is disconnected, then the
primitivity of $G$ implies that $\Gamma\cong{\mathbf{L}}_{n}$. Hence we may
assume that $\Gamma$ is connected. Moreover,
${\mathrm{RelFix}}(\Gamma)>\frac{1}{3}$ implies that $\mu(G)<\frac{2n}{3}$.
Hence $G$ is one of the groups determined in [8] and described in Theorem 24.

Suppose that $G$ is an almost simple group. Then $G$ is one of the groups
appearing in parts $(a)-(e)$ of Theorem 24. Since any $G$-vertex-primitive
group is a union of orbital digraphs for $G$, the digraphs arising from these
cases will be merged product action digraphs
${\mathcal{P}}(1,{\mathcal{G}},{\mathcal{J}})$ (see Remark 3). Hence, our goal
is to consider these almost simple groups in turn and compile their list of
orbitals digraphs ${\mathcal{G}}$.

Let $G$ be a group as described in Theorem 24 $(a)$. Lemma 20 states the
orbital digraphs for $G$ are the distance-$i$ Johnson graph
$\mathbf{J}(m,k,i)$.

Assume that $k=1$, that is, consider the natural action of either
${\mathrm{Alt}}(m)$ or ${\mathrm{Sym}}(m)$ of degree $m$. Since this action is
$2$-transitive, their set of orbital digraphs is
${\mathcal{G}}=\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m}\\}$. In particular,
${\mathcal{P}}(1,{\mathcal{G}},{\mathcal{J}})=\mathbf{H}(1,m,{\mathcal{J}})$.
This case exhausts the generalized Hamming graphs with $r=1$, which appear in
Theorem 8 $(i)$. Therefore, in view of Remark 6, for as long as we suppose
$r=1$, we can also assume that ${\mathcal{J}}$ is a non-Hamming homogeneous
set. Observe $m\geq 4$, otherwise, we go against our assumption on the
relative fixity.

Going back to distance-$i$ Johnson graphs, to guarantee that ${\mathcal{J}}$
is non-Hamming, we have to take $k\geq 2$. Thus,

${\mathcal{G}}=\left\\{\mathbf{J}(m,k,i)\mid
i\in\\{0,1,\ldots,k\\}\right\\}\,,$

which corresponds to Theorem 8 $(ii)(a)$.

Let $G={\mathrm{Sym}}(2m)$ be a permutation group from Theorem 24 $(b)$. If
$m=2$, the degree of $G$ is $3$, and the relative fixity of any action of
degree $3$ can either be $0$ or $\frac{1}{3}$. Hence, we must suppose that
$m\geq 3$: by Lemma 22, the orbital digraphs for $G$ are the squashed
distance-$i$ Johnson graph $\mathbf{QJ}(2m,m,i)$. We obtain that

${\mathcal{G}}=\left\\{\mathbf{QJ}(2m,m,i)\mid i\in\\{0,1,\ldots,\lfloor
m/2\rfloor\\}\right\\}\,,$

as described in Theorem 8 $(ii)(b)$.

Let $G=M_{22}:2$ in the action described in Theorem 24 $(c)$. Consulting the
list of all the primitive groups of degree $22$ in Magma [6] (which is based
on the list compiled in [11]), we realize that they are all $2$-transitive.
Hence, the set of orbital digraphs is
${\mathcal{G}}=\\{{\mathbf{K}}_{22},{\mathbf{L}}_{22}\\}$. In particular, all
the graphs are generalised Hamming graphs.

Let $G$ be an almost simple of Lie type appearing in Theorem 24 $(d)$. Since
all these groups are $2$-transitive with a $2$-transitive socle $L$, their
orbital digraphs are either ${\mathbf{K}}_{m}$ or ${\mathbf{L}}_{m}$, where
$m\geq 7$ is the degree of $G$. Once again, we obtain only generalise Hamming
graphs.

Let $G$ be an almost simple of Lie type described in Theorem 24 $(e)$. Any
group of permutational rank $3$ defines two nondiagonal orbital digraphs, and,
as such digraphs are arc-transitive and one the complement of the other, they
are strongly regular digraphs (see, for instance, [7, Section 1.1.5]). The set
of orbital digraphs is of the form
${\mathcal{G}}=\\{{\mathbf{L}}_{m},\Gamma_{1},\Gamma_{2}\\}$, where we listed
the possible $\Gamma_{1}$ in Section 4.4, and where $m=|V\Gamma_{1}|$. The
graphs described in this paragraph appear in Theorem 8 $(ii)(c)$.

We have exhausted the almost simple groups from Theorem 24. Hence, we pass to
Theorem 24 $(f)$. Suppose that $G\leq K\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$
is a primitive group of product action type. We want to apply Theorem 17 to
$G$. The only hypothesis we miss is that $T$ and $G_{\Delta}^{\Delta}$ share
the same set of orbital digraphs.

We claim that $T$ and $K$ induces the same set of orbital digraphs. If $K$ is
either alternating or symmetric, the claim follows from Lemmas 20 and 22. If
$K$ is $2$-transitive, then we can observe that its socle $L$ is also
$2$-transitive: the socle of $M_{22}:2$ is $T=M_{22}$ in its natural
$3$-transitive action, while the socle $T$ of the almost simple groups of Lie
type of rank $2$ is $2$-transitive by [9, Section 5]. In particular, $K$ and
$T$ both have ${\mathcal{G}}=\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m}\\}$ as their
set of orbital graphs. Finally, suppose that $K$ is an almost simple group of
permutational rank $3$. We have that its socle $T$ is also of permutational
rank $3$ by [17, Theorem 1.1]. Observe that, since any orbital digraph for $T$
is a subgraph of an orbital digraph for $G$, the fact that $G$ and $L$ both
have permutational rank $3$ implies that they share the same set of orbital
digraphs. Therefore, the claim is true.

By our claim together with the double inclusion

$T\leq G_{\Delta}^{\Delta}\leq K\,,$

we obtain that $T,G_{\Delta}^{\Delta}$ and $K$ all induce the same set of
orbital digraphs. Therefore, we can apply Theorem 17 to $G$: we obtain that
$G$ shares its orbital graphs with $T\mathop{\mathrm{wr}}G^{\Omega}$.

Therefore, all the $G$-vertex-primitive digraphs are union of orbital digraphs
for $T\mathop{\mathrm{wr}}H$, with $T$ socle type of $G$ and $H$ transitive
permutation group isomorphic to $G^{\Omega}$. In other words, we found all the
graphs ${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$ with $r\geq 2$ described
in Theorem 8. (Recall that, by Definition 4, among the graphs
${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$, we find all the generalised
Hamming graphs.)

Suppose that $G$ is an affine group with a regular normal socle $N$, which is
an elementary abelian $2$-subgroup. We have that $G$ can be written as the
split extension $N:H$, where $H$ is a group of matrices that acts irreducibly
on $N$. It follows that $G$ is $2$-transitive on $N$, hence, as $|N|\geq 4$,
the graphs arising in this scenario are
${\mathbf{L}}_{|N|},{\mathbf{K}}_{|N|}$ and
${\mathbf{L}}_{|N|}\cup{\mathbf{K}}_{|N|}$, which are generalised Hamming
graphs.

We have completed the first part of the proof, showing that the list of
vertex-primitive digraphs appearing in Theorem 8 is exhaustive. As all the
orbital digraphs in ${\mathcal{G}}$ are actually graphs, the same property is
true for the graphs in the list, as we have underlined in Remark 9.

We can now pass to the second part of the proof, that is, we can now tackle
the computation of relative fixities. We already took care of the generalised
Hamming graphs in Lemma 18. Thus, we can suppose that $\Gamma$ is a merged
product action graph ${\mathcal{P}}(r,{\mathcal{G}},{\mathcal{J}})$ appearing
in Theorem 8 $(ii)$.

Suppose that $r=1$, that is, $\Gamma$ is a union of graphs for some primitive
almost simple group $K$. (We are tacitely assuming that $K$ is maximal among
the groups appearing in a given part of Theorem 24.) In view of [21, Theorem],
we have that $K$ is a maximal subgroup of either ${\mathrm{Alt}}(|V\Gamma|)$
or ${\mathrm{Sym}}(|V\Gamma|)$. Therefore, there are just two options for
${\mathrm{Aut}}(\Gamma)$: either it is isomorphic to $K$ or it contains
${\mathrm{Alt}}(|V\Gamma|)$. In the latter scenario, as
${\mathrm{Alt}}(|V\Gamma|)$ is $2$-transitive on the vertices, we obtain that
$\Gamma\in\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m},{\mathbf{L}}_{m}\cup{\mathbf{K}}_{m}\\}$.
All those graphs are generalised Hamming graphs, against our assumption on
$\Gamma$. Therefore, we have $K={\mathrm{Aut}}(\Gamma)$. In particular, the
relative fixity for $\Gamma$ are computed in Lemma 21, Lemma 23 or Table 1
given that ${\mathcal{G}}$ is described in Theorem 8 $(ii)(a)$, $(ii)(b)$ or
$(ii)(c)$ respectively.

Suppose now that $r\geq 2$. The automorphism group of $\Gamma$ either embeds
into ${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$, where
$m=|V\Gamma_{i}|$ for any $\Gamma_{i}\in{\mathcal{G}}$, or, by maximality of
${\mathrm{Sym}}(m)\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$,
${\mathrm{Aut}}(\Gamma)={\mathrm{Sym}}(m^{r})$. In the latter scenario,
$\Gamma\in\\{{\mathbf{L}}_{m},{\mathbf{K}}_{m},{\mathbf{L}}_{m}\cup{\mathbf{K}}_{m}\\}$.
All these graphs can be written as a merged product graph where $r=1$ and
${\mathcal{J}}$ is a Hamming set. This goes against our assumption on
$\Gamma$, thus we must suppose
${\mathrm{Aut}}(\Gamma)\neq{\mathrm{Sym}}(m^{r})$.

As a consequence, we obtain that, for some almost simple group $K$ listed in
Theorem 24 $(a)-(e)$, and for some transitive group $H\leq{\mathrm{Sym}}(r)$,
$K\mathop{\mathrm{wr}}H\leq{\mathrm{Aut}}(\Gamma)$. Note that, as
$K\leq{\mathrm{Aut}}(\Gamma)^{\Delta}_{\Delta}$, by [21, Theorem],
${\mathrm{Aut}}(\Gamma)^{\Delta}_{\Delta}$ is either $K$ or it contains
${\mathrm{Alt}}(m)$. If the latter case occurs, then
${\mathrm{Alt}}(m)^{r}\mathop{\mathrm{wr}}H\leq{\mathrm{Aut}}(\Gamma)$. By
Lemma 18, $\Gamma$ is a generalised Hamming graph, which contradicts our
choice of $\Gamma$. Therefore, ${\mathrm{Aut}}(\Gamma)\leq
K\mathop{\mathrm{wr}}{\mathrm{Sym}}(r)$.

Observe that we can apply Lemma 19. We obtain that

${\mathrm{RelFix}}(\Gamma)=1-\frac{\mu(K)m^{r-1}}{m^{r}}=1-\frac{\mu(K)}{m}={\mathrm{RelFix}}\left({\mathcal{P}}(1,{\mathcal{G}},{\mathcal{J}}^{\prime})\right)\,,$

for some non-Hamming homogeneous set ${\mathcal{J}}^{\prime}$. In particular,
the relative fixities for $r\geq 2$ coincides with those we have already
computed for $r=1$. This complete the proof. ∎

##  6\. Proof of Theorem 12

Recall that a permutation group $G$ on $\Omega$ is _quasiprimitive_ if all its
normal subgroups are transitive on $\Omega$. Clearly, any primitive group is
quasiprimitive. Moreover, recall that, by repeating the proof of
Cauchy–Frobenius Lemma (see [12, Theorem 1.7A]) on the conjugacy class of a
permutation $x\in G$, we get

${\mathrm{fix}}(x)|x^{G}|=|x^{G}\cap G_{\omega}|$

where ${\mathrm{fix}}(x)=|\Omega|-|\mathrm{supp}(x)|$ is the number of fixed
points of $x$.

###### Proof of Theorem 12.

(We would like to thank P. Spiga again for pointing out the key ingredients
for this proof.) Let $G$ be a quasiprimitive permutation group on a set
$\Omega$, and let $x\in G\setminus\\{1\\}$ be an element achieving
$|\mathrm{supp}(x)|\leq(1-\alpha)|\Omega|$. For any point $\omega\in\Omega$,
we obtain

$\alpha\leq\frac{|x^{G}\cap
G_{\omega}|}{|x^{G}|}\leq\frac{|G_{\omega}|}{|x^{G}|}\leq\frac{\beta}{|x^{G}|}\,.$

It follows that $|x^{G}|\leq\alpha^{-1}\beta$. Now consider the normal
subgroup of $G$ defined by

$N:=\bigcap\limits_{g\in G}\mathbf{C}_{G}(x^{g})\,.$

Recall that $|G:\mathbf{C}_{G}(x)|=|x^{G}|$. Observe that $G$ acts by
conjugation on the set

$\\{\mathbf{C}_{G}(x^{g})\mid g\in G\\}\,,$

it defines a single orbit of size $|x^{G}|$, and $N$ is the kernel of this
action. Therefore

$|G:N|\leq|x^{G}|!\leq\left\lceil\frac{\beta}{\alpha}\right\rceil!\,,$

that is, $N$ is a bounded index subgroup of $G$. Since $G$ is quasiprimitive,
either $N$ is trivial or $N$ is transitive. Aiming for a contradiction, we
suppose that $N$ is transitive. Since $[N,x]=1$, for any $\omega\in\Omega$ and
for any $n\in N$,

$\omega^{nx}=\omega^{xn}=\omega^{n}\,.$

The transitivity of $N$ implies that $x=1$, against our choice of $x$.
Therefore, $N$ is trivial. It follows that

$|G|=|G:N|\leq\left\lceil\frac{\beta}{\alpha}\right\rceil!\,.$

Since there are finitely many abstract groups of bounded size, the proof is
complete. ∎

An equivalent formulation of Sims’ Conjecture states that if $G$ is a
primitive permutation group and the minimal out-valency among its nondiagonal
orbital digraphs is at most $d$, then the size of a point stabilizer is
bounded from above by a function $\mathbf{f}(d)$ depending only on the
positive integer $d$. An answer in the positive to this conjecture was given
in [10].

###### Proof of Corollary 13.

Let $\Gamma$ be a vertex-primitive digraphs of out-valency at most $d$ and
relative fixity exceeding $\alpha$, and let $G={\mathrm{Aut}}(\Gamma)$. The
hypothesis on the out-valency implies that, for any $v\in V\Gamma$,
$|G_{v}|\leq\mathbf{f}(d)$, where $\mathbf{f}(d)$ is the function that solves
Sims’ Conjecture. The result thus follows by choosing $\beta=\mathbf{f}(d)$ in
Theorem 12. ∎

We conclude the paper by observing that, as $\mathbf{f}(d)\geq(d-1)!$, from
Corollary 13 we cannot obtain a bound as sharp as that in Remark 11.

## References

  * [1] L. Babai.  On the order of uniprimitive permutation groups.  Annals of Mathematics, 113(3):553–568, 1981.
  * [2] L. Babai.  On the automorphism groups of strongly regular graphs I.  In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, pages 359–368, New York, NY, USA, 2014\. Association for Computing Machinery.
  * [3] L. Babai.  Graph isomorphism in quasipolynomial time.  2015\.  arXiv:1512.03547.
  * [4] L. Babai.  On the automorphism groups of strongly regular graphs II.  Journal of Algebra, 421:560–578, 2015.  Special issue in memory of Ákos Seress.
  * [5] M. Barbieri, V. Grazian, and P. Spiga.  On the number of fixed edges of automorphisms of vertex-transitive graphs of small valency.  Journal of Algebraic Combinatorics, 57:329–348, 2023.
  * [6] W. Bosma, J. Cannon, and C. Playoust.  The Magma algebra system. I. The user language.  Journal of Symbolic Computation, 24(3-4):235–265, 1997.  Computational algebra and number theory (London, 1993).
  * [7] A. E. Brouwer and H. Van Maldeghem.  Strongly regular graphs, volume 182 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, 2022.
  * [8] T. C. Burness and R. M. Guralnick.  Fixed point ratios for finite primitive groups and applications.  Advances in Mathematics, 411:108778, 2022.
  * [9] P. J. Cameron.  Finite permutation groups and finite simple groups.  Bulletin of the London Mathematical Society, 13(1):1–22, 1981.
  * [10] P. J. Cameron, C. E. Praeger, J. Saxl, and G. M. Seitz.  On the Sims Conjecture and distance transitive graphs.  Bulletin of the London Mathematical Society, 15(5):499–506, 1983\.
  * [11] H. J. Coutts, M. Quick, and C. M. Roney-Dougal.  The primitive permutation groups of degree less than $4\,096$.  Communications in Algebra, 39(10):3526–3546, 2011.
  * [12] J. D. Dixon and B. Mortimer.  Permutation Groups, volume 163 of Graduate Texts in Mathematics.  Springer, New York, 1996.
  * [13] R. Guralnick and K. Magaard.  On the minimal degree of a primitive permutation group.  Journal of Algebra, 207(1):127–145, 1998.
  * [14] W. Imrich and S. Klavžar.  Product Graphs: Structure and Recognition.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2000.
  * [15] G. A. Jones.  Automorphisms and regular embeddings of merged johnson graphs.  European Journal of Combinatorics, 26(3):417–435, 2005.  Topological Graph Theory and Graph Minors, second issue.
  * [16] G. A. Jones and R. Jaycay.  Cayley properties of merged Johnson graphs.  Journal of Algebraic Combinatorics, 44:1047–1067, 2016.
  * [17] W. M. Kantor and R. A. Liebler.  The rank $3$ permutation representation of the finite classical groups.  Transactions of the American Mathematical Society, 271(1):1–71, 1982.
  * [18] L. G. Kovács.  Wreath decompositions of finite permutation groups.  Bulletin of the Australian Mathematical Society, 40(2):255–279, 1989.
  * [19] F. Lehner, P. Potočnik, and P. Spiga.  On fixity of arc-transitive graphs.  Science China Mathematics, 64:2603–2610, 2021.
  * [20] M. W. Liebeck.  On minimal degrees and base sizes of primitive permutation groups.  Archiv der Mathematik, 43:11–15, 1984.
  * [21] M. W. Liebeck, C. E. Praeger, and J. Saxl.  A classification of the maximal subgroups of the finite alternating and symmetric groups.  Journal of Algebra, 111(2):365–383, 1987.
  * [22] M. W. Liebeck, C. E. Praeger, and J. Saxl.  On the O’Nan–Scott theorem for finite primitive permutation groups.  Journal of the Australian Mathematical Society, 44(3):389–396, 1988\.
  * [23] M. W. Liebeck and J. Saxl.  Minimal degrees of primitive permutation groups, with an application to monodromy groups of covers of riemann surfaces.  Proceedings of the London Mathematical Society, s3-63(2):266–314, 1991.
  * [24] M. W. Liebeck and A. Shalev.  Simple groups, permutation groups, and probability.  Journal of the American Mathematical Society, 12:497–520, 1999\.
  * [25] P. Potočnik and P. Spiga.  On the number of fixed points of automorphisms of vertex-transitive graphs.  Combinatorica, 41:703–747, 2021.
  * [26] C. E. Praeger and C. Schneider.  Embedding permutation groups into wreath products in product action.  Journal of the Australian Mathematical Society, 92(1):127–136, 2012\.