# The non-commuting, non-generating graph
of a finite simple group

Saul D. Freedman  School of Mathematics and Statistics, University of St
Andrews, St Andrews, KY16 9SS, UK<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a group such that $G/Z(G)$ is finite and simple. The _non-
commuting, non-generating graph_ $\Xi(G)$ of $G$ has vertex set $G\setminus
Z(G)$, with edges corresponding to pairs of elements that do not commute and
do not generate $G$. We show that $\Xi(G)$ is connected with diameter at most
$5$, with smaller upper bounds for certain families of groups. When $G$ itself
is simple, we prove that the diameter of the complement of the generating
graph of $G$ has a tight upper bound of $4$. In the companion paper [16], we
consider $\Xi(G)$ when $G/Z(G)$ is not simple.

###### 2020 Mathematics Subject Classification:

Primary: 20E32; Secondary: 20D60, 05C25

Keywords: simple groups; non-commuting non-generating graph; non-generating
graph; generating graph; graphs defined on groups

##  1\. Introduction

The generating graph of a group $G$ has been investigated by many authors
(e.g., [3, 5, 13]), and encodes information about the generating pairs for
$G$. The complement of this graph has also been studied (e.g., in [31]), and
for $G$ non-abelian, its edge set necessarily includes all pairs of non-
commuting elements. The remaining non-generating pairs are described by the
_non-commuting, non-generating graph_ $\Xi(G)$ of $G$, with vertex set
$G\setminus Z(G)$ and $\\{x,y\\}$ an edge if and only if $[x,y]\neq 1$ and
$\langle x,y\rangle\neq G$. Both the generating graph and $\Xi(G)$ are
differences between consecutive graphs in Cameron’s [9, §2.6] hierarchy of
graphs.

The graph $\Xi(G)$ was introduced in [10], where its connectedness and
diameter were investigated for nilpotent groups (and more generally, for
groups with all maximal subgroups normal). In our companion paper [16], we
extend these results to the general case where $G/Z(G)$ is not simple. See
these two papers for further details on our motivation for studying the graph.

In this paper, we address the case where $G/Z(G)$ is finite and (non-abelian)
simple. Our main theorem assumes that $G$ itself is simple. Here,
$\mathrm{diam}(\Xi(G))$ denotes the diameter of $\Xi(G)$, which is always at
least $2$, since no vertex is adjacent to any of its powers.

######  Theorem 1.1.

Let $G$ be a non-abelian finite simple group.

  1. (i)

$\Xi(G)$ is connected with diameter at most $5$.

  2. (ii)

If $G$ is a sporadic simple group or the Tits group, then
$\mathrm{diam}(\Xi(G))\leqslant 4$.

  3. (iii)

For certain simple groups $G$, Table 1 lists exact values or upper bounds for
$\mathrm{diam}(\Xi(G))$.

Table 1. Exact values or upper bounds for $\mathrm{diam}(\Xi(G))$, for certain simple groups $G$. Here, $n$ is a positive integer and $q$ is a prime power. $G$ | $\mathrm{diam}(\Xi(G))$
---|---
$\mathrm{M}_{11},\mathrm{M}_{12},\mathrm{M}_{22},\mathrm{J}_{2}$ | $2$
$\mathrm{M}_{23},\mathrm{J_{1}}$ | $3$
$\mathbb{B},\mathrm{PSU}(7,2)$ | $4$
$A_{n}$; $n$ even | $\leqslant 3$
$A_{n}$; $n$ odd | $\leqslant 4$
$\mathrm{PSL}(n,q),\mathrm{Sz}(q)$ | $\leqslant 4$
$G_{2}(q),{}^{2}G_{2}(q),{}^{3}D_{4}(q),F_{4}(q),E_{8}(q)$; $q$ odd | $\leqslant 4$

In particular, when $G$ is non-abelian, finite and simple,
$\mathrm{diam}(\Xi(G))$ may be larger than the diameter of the group’s
generating graph, which is equal to $2$ by [3, Theorem 1.2].

######  Remark 1.2.

Our proof of Theorem 1.1 involves Theorem 4.6, on subspace stabilisers in
simple unitary groups. In [18, Ch. 3], we prove similar results on larger
families of finite almost simple classical groups, to obtain lower bounds for
the base sizes of their primitive subspace actions.

######  Remark 1.3.

It is easy to deduce the connectedness and diameter of the non-commuting, non-
generating graphs of certain infinite simple groups $G$. For instance, if $G$
is a _Tarski monster_ , then each nontrivial proper subgroup of $G$ has order
a fixed prime, and so each vertex of $\Xi(G)$ is isolated. Additionally, by
[10, Corollary 7], $\mathrm{diam}(\Xi(G))=2$ whenever $G$ is not
$2$-generated.

Now, if $G/Z(G)$ is simple, then $Z(G)x$ is a vertex of $\Xi(G/Z(G))$ whenever
$x\in G\setminus Z(G)$. Thus [16, Lemma 2.9(ii)] yields the following
corollary of Theorem 1.1(i).

######  Corollary 1.4.

Let $G$ be a group such that $G/Z(G)$ is finite and simple. Then $\Xi(G)$ is
connected with diameter at most $\mathrm{diam}(\Xi(G/Z(G)))\leqslant 5$.

We note that our proof of Theorem 1.1(i) relies on the classification of
finite simple groups. In §2.2, we prove the following special case that does
not depend on the classification.

######  Proposition 1.5.

Let $G$ be a non-abelian finite simple group, and suppose that every maximal
subgroup of $G$ has even order. Then $\Xi(G)$ is connected with diameter at
most $5$.

We will present examples of diameters achieved by various simple groups,
computed using Magma [1]. Notably, none of our examples meet the upper bounds
in rows 4–7 of Table 1.

######  Question 1.6.

Are the upper bounds for $\mathrm{diam}(\Xi(G))$ given in rows 4–7 of Table 1
tight? If not, what are the best possible upper bounds?

######  Question 1.7.

Does there exist a non-abelian finite simple group $G$ such that
$\mathrm{diam}(\Xi(G))=5$? In addition, for which non-abelian finite simple
groups $G$ is $\mathrm{diam}(\Xi(G))$ equal to $4$?

Finally, we will prove the following analogue of Theorem 1.1 for the _non-
generating graph_ $\overline{\Gamma}(G)$ of a non-abelian finite simple group
$G$. This graph is the complement of the generating graph of $G$, and has
vertex set $G\setminus\\{1\\}$, with vertices $x$ and $y$ adjacent if and only
if $\langle x,y\rangle\neq G$. Note that $\Xi(G)$ is a spanning subgraph of
$\overline{\Gamma}(G)$ (since $Z(G)=1$).

######  Theorem 1.8.

Let $G$ be a non-abelian finite simple group. Then $\overline{\Gamma}(G)$ is
connected with diameter at most $4$, or at most $3$ if every maximal subgroup
of $G$ has even order. Furthermore, if $G$ is the baby monster group or
$\mathrm{PSU}(7,2)$, then $\mathrm{diam}(\overline{\Gamma}(G))=4$.

An earlier version of this theorem is a key component of the proof of [31,
Theorem 1], which investigates the connectedness and diameter of
$\overline{\Gamma}(G)$ for a finite group $G$. This graph is closely related
to the _soluble graph_ of $G$, most recently studied in [8]; see Remark 7 in
that paper.

The remainder of this paper is structured as follows. The focus of §2 is on
preliminary results, and includes a proof of Proposition 1.5. In §3, we prove
the alternating, sporadic and exceptional cases of Theorem 1.1. We explore
matrices and stabilisers of subspaces in linear and unitary groups in §4, and
then apply our results in §5 to prove Theorem 1.1 for those groups.
Additionally, §5 concludes with a proof of Theorem 1.8.

##  2\. Preliminaries

Here, we present preliminary results on the non-commuting, non-generating
graph of a group, and on maximal subgroups of finite simple groups; in
particular, we prove Proposition 1.5.

###  2.1. The non-commuting, non-generating graph

In this subsection, $G$ is an arbitrary group, unless specified otherwise.
Given vertices $x$ and $y$ of a graph $\Gamma$, we denote the distance in
$\Gamma$ between $x$ and $y$ by $d(x,y)$, and if $x$ and $y$ are adjacent,
then we write $x\sim y$.

######  Lemma 2.1 ([10, Corollary 6]).

Let $H$ be a proper non-abelian subgroup of $G$. Then the induced subgraph of
$\Xi(G)$ corresponding to $H\setminus Z(H)$ is connected with diameter $2$.

######  Lemma 2.2 ([16, Lemma 2.9(i)]).

Let $N$ be a normal subgroup of $G$, and $x,y\in G$. Then $\\{Nx,Ny\\}$ is an
edge of $\Xi(G/N)$ if and only if $[x,y]\notin N$ and $\langle
x,y,N\rangle<G$.

######  Proposition 2.3.

Suppose that $G$ is finite and insoluble. Then $\Xi(G)$ has no isolated
vertices, and each element of $G\setminus Z(G)$ is a non-central element of
some maximal subgroup.

###### Proof.

By [24], $G$ has no abelian maximal subgroup. Thus [16, Proposition 2.6] and
[10, Proposition 9] yield the result. ∎

Our next result highlights a connection between $\Xi(G)$ and the _intersection
graph_ $\Delta_{G}$ of $G$. This latter graph, introduced in [14], has vertex
set the proper nontrivial subgroups of $G$, with subgroups adjacent if and
only if they intersect nontrivially.

######  Lemma 2.4.

Let $\Gamma$ be equal to $\Xi(G)$ or the non-generating graph of $G$.
Additionally, suppose that $Z(G)=1$, and that $\Gamma$ is connected with
finite diameter. Then
$\mathrm{diam}(\Gamma)\geqslant\mathrm{diam}(\Delta_{G})-1$.

###### Proof.

By Propositions 12.1 and 2.3 of [9] (which assume that $G$ is finite, but
whose proofs also hold for infinite groups), the diameters of $\Delta_{G}$ and
the non-generating graph of $G$ differ by at most one. As $Z(G)$ is trivial,
$\Xi(G)$ is a spanning subgraph of the non-generating graph of $G$, and so the
diameter of the former is at least the diameter of the latter. ∎

###  2.2. Maximal subgroups of non-abelian finite simple groups

Assume throughout this subsection that $G$ is non-abelian, finite and simple.

######  Lemma 2.5.

Let $L$ and $M$ be maximal subgroups of $G$, with $|L|$ even.

  1. (i)

If $Z(L)$ contains an involution $a$, then $L\setminus Z(L)$ contains a
$G$-conjugate of $a$.

  2. (ii)

$L$ contains an involution that does not lie in $Z(L)\cup Z(M)$.

  3. (iii)

Suppose that $|M|$ is even, and let $a$ be an involution of $L\setminus M$.
Then $M\setminus Z(M)$ contains an involution $b$ that does not commute with
$a$.

  4. (iv)

Suppose that $L\cap M$ lies in $Z(M)$ and contains an involution $f$.
Additionally, let ${u\in L\setminus M}$. Then $L\setminus M$ contains an
involution $f^{\prime}$ with $[u,f^{\prime}]\neq 1$.

###### Proof.

(i) Suppose that $Z(L)$ contains an involution $a$, so that $C_{G}(a)=L$. By
[20, Corollary 1], there exists $g\in G$ such that $a\neq a^{g}\in
C_{G}(a)=L$. In fact, $g\notin L$, as $a\in Z(L)$. Thus $L\neq
L^{g}=C_{G}(a^{g})$, and so the involution $a^{g}$ is non-central in $L$.

(ii) We will prove that $L$ contains an involution $s\notin Z(L)\cup Z(M)$. By
(i), there exists an involution $y\in L\setminus Z(L)$. If $y\notin Z(M)$,
then we can set $s=y$. If instead $y\in Z(M)$ (so that $L\neq M$), then
$C_{G}(y)=M$. Additionally, since $Z(L)$ and $L\cap M$ are proper subgroups of
$L$, there exists $h\in L\setminus(Z(L)\cup M)$, and $y^{h}$ is a non-central
involution of $L$. Moreover, $M\neq M^{h}=C_{G}(y^{h})$. Therefore,
$y^{h}\notin Z(M)$, and so we can set $s=y^{h}$.

(iii) Suppose first that $|Z(M)|$ is odd, let $S$ be the set of involutions of
$M$, and let
$Q_{M}\mathrel{\mathchoice{\ooalign{\raisebox{1.06805pt}{$\displaystyle\lhd$}\cr$\displaystyle\leqslant$\cr}}{\ooalign{\raisebox{1.06805pt}{$\textstyle\lhd$}\cr$\textstyle\leqslant$\cr}}{\ooalign{\raisebox{0.60764pt}{$\scriptstyle\lhd$}\cr$\scriptstyle\leqslant$\cr}}{\ooalign{\raisebox{0.43402pt}{$\scriptscriptstyle\lhd$}\cr$\scriptscriptstyle\leqslant$\cr}}}M$
be the subgroup generated by $S$. If the involution $a\in L\setminus M$
commutes with each element of $S$, then $a\in C_{G}(Q_{M})$, and so
$Q_{M}\mathrel{\mathchoice{\ooalign{\raisebox{1.06805pt}{$\displaystyle\lhd$}\cr$\displaystyle\leqslant$\cr}}{\ooalign{\raisebox{1.06805pt}{$\textstyle\lhd$}\cr$\textstyle\leqslant$\cr}}{\ooalign{\raisebox{0.60764pt}{$\scriptstyle\lhd$}\cr$\scriptstyle\leqslant$\cr}}{\ooalign{\raisebox{0.43402pt}{$\scriptscriptstyle\lhd$}\cr$\scriptscriptstyle\leqslant$\cr}}}\langle
M,a\rangle=G$, contradicting the simplicity of $G$. Thus there exists $r\in
S\setminus C_{G}(a)$. As $S\cap Z(M)=1$, we can set $b=r$.

If instead $Z(M)$ contains an involution $z$, then by applying (i) to $M$, we
deduce that $M\setminus Z(M)$ contains an involution $c$. If $[a,c]\neq 1$,
then we can set $b=c$. Otherwise, as $a\notin M=C_{G}(z)$, we see that
$[a,zc]=[a,z]^{c}\neq 1$. Thus we may set $b$ to be the involution $zc\in
M\setminus Z(M)$.

(iv) Let $s$ be the involution from (ii), so that $s\in L$ and $s\notin L\cap
M\leqslant Z(M)$. If $[u,s]\neq 1$, then we can set $f^{\prime}=s$. Assume
therefore that $[u,s]=1$. Since $C_{G}(f)=M$ and $C_{G}(f^{s})=M^{s}\neq M$,
we obtain $f^{s}\in L\setminus Z(M)$, and hence $f^{s}\notin L\cap M$. If
$f^{s}\in C_{G}(u)$, then $C_{L}(u)$ contains $\langle s,f^{s}\rangle$, which
contains $f$. This contradicts $u\notin M=C_{G}(f)$, and so we can set
$f^{\prime}=f^{s}$. ∎

The following lemma is one of the main ingredients in the proof of Theorem
1.1.

######  Lemma 2.6.

Let $L$ and $M$ be maximal subgroups of $G$ of even order, and let $x\in
L\setminus Z(L)$ and $y\in M\setminus Z(M)$. Then $d(x,y)\leqslant 5$.
Moreover, if $L$ contains an involution $a$ such that $d(x,a)\leqslant 1$,
then $d(x,y)\leqslant 4$.

###### Proof.

We will use Lemma 2.1 several times in this proof without further reference.
First, we may assume that $L\neq M$, as otherwise $d(x,y)\leqslant 2$. Lemma
2.5(i) shows that the set $\mathcal{A}$ of involutions in $L\setminus Z(L)$ is
non-empty. Additionally, $d(x,u)\leqslant 2$ for all $u\in\mathcal{A}$. Choose
$a\in\mathcal{A}$ so that $d(x,a)=\underset{u\in\mathcal{A}}{\min}\,d(x,u)$.
No element of $Z(L)$ is adjacent to $x$ in $\Xi(G)$, and so if $d(x,a)>1$,
then $x$ is neither equal nor adjacent to any involution of $L$. We split the
remainder of the proof into three cases, depending on where $a$ lies with
respect to $M$ and $Z(M)$.

Case (a): $a\in M\setminus Z(M)$. Here, $d(a,y)\leqslant 2$, and so
$d(x,y)\leqslant d(x,a)+d(a,y)\leqslant 4$.

Case (b): $a\notin M$. By Lemma 2.5(iii), there exists an involution $b\in
M\setminus Z(M)$ such that $[a,b]\neq 1$. As $\langle a,b\rangle$ is dihedral,
$a\sim b$. Since $d(x,a),d(b,y)\leqslant 2$, we conclude that $d(x,y)\leqslant
5$. Moreover, if $d(x,a)\leqslant 1$, then $d(x,y)\leqslant 4$.

Case (c): $a\in Z(M)$. Here, $M=C_{G}(a)$, and Lemma 2.5(ii) yields an
involution $a^{\prime}\in\mathcal{A}\setminus Z(M)$. Hence we can replace $a$
by $a^{\prime}$ in the arguments in Cases (a) and (b) to deduce that
$d(x,y)\leqslant 5$, with $d(x,y)\leqslant 4$ if either $a^{\prime}\in M$ or
$d(x,a^{\prime})\leqslant 1$.

It remains to show (in the case $a\in Z(M)$) that if $d(x,a)\leqslant 1$,
$a^{\prime}\notin M=C_{G}(a)$, and $d(x,a^{\prime})>1$, then $d(x,y)\leqslant
4$. Since $a^{\prime}\notin C_{G}(a)$ and $x,a^{\prime}\in L$, we may assume
that $x\neq a$, as otherwise $d(x,a^{\prime})=1$. Thus $d(x,a)=1$, and so
$x\notin C_{G}(a)=M$.

Suppose first that $L\cap M\leqslant Z(M)$. Since $x\in L\setminus M$, and
since $a$ is an involution of $Z(M)$, Lemma 2.5(iv) shows that $x\sim
f^{\prime}$ for some involution $f^{\prime}\in L\setminus M$. In particular,
$f^{\prime}\in\mathcal{A}$, and we can replace $a$ with $f^{\prime}$ in the
argument in Case (b) to deduce that $d(x,y)\leqslant 4$.

Finally, suppose that there exists $c\in(L\cap M)\setminus Z(M)$. As
$a\in(L\cap M)\setminus C_{G}(x)$, there exists an $h\in L\cap M$ centralising
neither $M$ nor $x$. Thus $d(h,y)\leqslant 2$ and $x\sim h$, and so
$d(x,y)\leqslant 3$. ∎

###### Proof of Proposition 1.5.

For each $x\in\Xi(G)$, Proposition 2.3 gives $x\in K\setminus Z(K)$ for some
maximal subgroup $K$ of $G$ (of even order). Thus
$\mathrm{diam}(\Xi(G))\leqslant 5$ by Lemma 2.6. ∎

As the proofs of [20, Corollary 1] and Proposition 2.3 are independent of the
classification of finite simple groups, so are the proofs of Lemmas 2.5 and
2.6 and Proposition 1.5.

To prove Theorem 1.1(i), it remains to consider the non-abelian finite simple
groups that contain maximal subgroups of odd order.

######  Theorem 2.7 ([17, Proof of Theorem 1.1]).

The group $G$ has a maximal subgroup of odd order if and only if $G$ is
isomorphic to one of:

  1. (i)

$A_{p}$, with $p$ prime, $p\equiv 3\pmod{4}$ and $p\notin\\{7,11,23\\}$;

  2. (ii)

$\mathrm{PSL}(n,q)$, with $n$ prime, $(n,q)\neq(3,4)$, and $q\equiv 3\pmod{4}$
if $n=2$;

  3. (iii)

$\mathrm{PSU}(n,q)$, with $n$ an odd prime and
$(n,q)\notin\\{(3,3),(3,5),(5,2)\\}$; or

  4. (iv)

the Mathieu group $\mathrm{M}_{23}$, the Thompson group $\mathrm{Th}$, or the
baby monster group $\mathbb{B}$.

##  3\. Alternating, sporadic and exceptional simple groups

In this section, we prove the alternating, sporadic and exceptional cases of
Theorem 1.1. Note that we consider the Tits group ${}^{2}F_{4}(2)^{\prime}$
together with the sporadic groups.

###  3.1. Alternating groups

Let $G$ be the alternating group $A_{n}$ of degree $n\geqslant 5$. We will
prove the following result by considering the standard action of $G$ on the
set $\Omega:=\\{1,2,\ldots,n\\}$.

######  Theorem 3.1.

The graph $\Xi(G)$ of the alternating group $G$ of degree $n\geqslant 5$ is
connected with diameter at most $4$, or at most $3$ if $n$ is even.

######  Remark 3.2.

It is easy to adapt the proofs in this subsection to show that $\Xi(S_{n})$ is
connected. Hence [16, Theorem 1.2] implies that every such graph has diameter
at most $3$. Using Magma, we can show that this upper bound is achieved, for
example, by the graphs of $S_{5}$, $S_{7}$ and $S_{9}$.

Recall that a _derangement_ of $G$ is an element with no fixed points.

######  Lemma 3.3.

Let $x$ be a derangement of $G$ with at least two orbits on $\Omega$. In
addition, let $\\{\alpha_{1},\alpha_{2}\\}$ and $\\{\beta_{1},\beta_{2}\\}$ be
$2$-subsets of distinct orbits of $\langle x\rangle$ on $\Omega$. Finally, if
$\langle x\rangle$ has exactly two orbits on $\Omega$, then let
$g:=(\alpha_{1},\alpha_{2})(\beta_{1},\beta_{2})$, and otherwise, let
$g:=(\alpha_{1},\alpha_{2},\beta_{1})$. Then $x\sim g$.

###### Proof.

If $\langle x\rangle$ has exactly two orbits on $\Omega$, then at least one of
these orbits has length at least three. Hence, in each case, $x^{g}\neq x$,
and so $[x,g]\neq 1$. Additionally, $\langle x,g\rangle$ acts intransitively
on $\Omega$ and is therefore a proper subgroup of $G$. Thus $x\sim g$. ∎

######  Lemma 3.4.

Let $x,y\in G\setminus\\{1\\}$. Then $d(x,y)\leqslant 4$. If $d(x,y)\geqslant
3$, then at least one of $x$ and $y$ is a derangement, and if $d(x,y)=4$, then
both are derangements.

###### Proof.

Let $\alpha$ and $\beta$ be distinct points in $\Omega$. The point stabiliser
$G_{\alpha}\cong A_{n-1}$ is a maximal subgroup of $G$. As $Z(G_{\alpha})=1$,
it follows from Lemma 2.1 that $d(g,h)\leqslant 2$ for all $g,h\in
G_{\alpha}\setminus\\{1\\}$. Additionally, $H:=G_{\alpha}\cap G_{\beta}\cong
A_{n-2}$ is maximal in each of $G_{\alpha}$ and $G_{\beta}$. Let $g\in
G_{\alpha}$ and $k\in G_{\beta}$, such that $g,k\notin H$. Then $C_{H}(g)<H$,
as otherwise $\langle H,g\rangle=G_{\alpha}$ would centralise $g$. Similarly,
$C_{H}(k)<k$. Hence some element of $H$ centralises neither $g$ nor $k$, and
it follows that $d(g,k)\leqslant 2$.

To complete the proof, we will show that each derangement $x\in G$ is adjacent
in $\Xi(G)$ to some non-derangement. This follows immediately from Lemma 3.3
if $\langle x\rangle$ has at least two orbits on $\Omega$. Assume therefore
that $\langle x\rangle$ acts transitively on $\Omega$. Then $x$ is an
$n$-cycle $(\alpha_{1},\ldots,\alpha_{n})$, with $\alpha_{i}\in\Omega$ for
each $i$, and $n$ is odd. It suffices to prove that there exists $y\in
N_{G_{\alpha_{1}}}(\langle x\rangle)$ with $x^{y}\neq x$; it will then follow
that $\langle x,y\rangle\leqslant N_{G}(\langle x\rangle)<G$ and $[x,y]\neq
1$, so that $x\sim y$. For each $n$-cycle $r\in\langle x\rangle$ with $r\neq
x$, there exists an element $s\in N_{(S_{n})_{\alpha_{1}}}(\langle x\rangle)$
such that $x^{s}=r$. There are $\phi(n)-1>1$ of these $n$-cycles, where $\phi$
is Euler’s totient function. In fact, there exist $s,s^{\prime}\in
N_{(S_{n})_{\alpha_{1}}}(\langle x\rangle)$ such that $x^{s}=x^{-1}$ and
$x^{s^{\prime}}=x^{i}$ for some $i\in\\{2,\ldots,n-2\\}$. Since
$x^{ss^{\prime}}=x^{-i}\neq x$, we can choose $y\in
G\cap\\{s,s^{\prime},ss^{\prime}\\}\neq\varnothing$. ∎

We will write $\mathrm{supp}(g)$ to denote the support
$\\{\alpha\in\Omega\mid\alpha^{g}\neq\alpha\\}$ of an element $g\in G$.

######  Lemma 3.5.

Let $x$ and $y$ be derangements of $G$ such that each of $\langle x\rangle$
and $\langle y\rangle$ has at least two orbits on $\Omega$. Then
$d(x,y)\leqslant 3$.

###### Proof.

Let $\\{\alpha_{1},\alpha_{2}\\}$ and $B:=\\{\beta_{1},\beta_{2}\\}$ be
$2$-subsets of distinct orbits of $\langle x\rangle$ on $\Omega$, such that
$|\alpha_{1}^{\langle x\rangle}|\geqslant|\beta_{1}^{\langle x\rangle}|$, and
let $\\{\gamma_{1},\gamma_{2}\\}$ and $D:=\\{\delta_{1},\delta_{2}\\}$ be
$2$-subsets of distinct orbits of $\langle y\rangle$ on $\Omega$. We may
assume that $\alpha_{1}=\gamma_{1}$. If $n=5$, then each of $\langle x\rangle$
and $\langle y\rangle$ has exactly two orbits on $\Omega$.

Case (a): $\langle x\rangle$ and $\langle y\rangle$ each have exactly two
orbits on $\Omega$. We see from Lemma 3.3 that $x\sim
a:=(\alpha_{1},\alpha_{2})(\beta_{1},\beta_{2})$ and $y\sim
b:=(\alpha_{1},\gamma_{2})(\delta_{1},\delta_{2})$. In particular, if $a=b$,
then $d(x,y)\leqslant 2$.

Assume therefore that $a\neq b$, and hence either $\alpha_{2}\neq\gamma_{2}$
or $B\neq D$. If $[a,b]=1$, then either $\gamma_{2}=\alpha_{2}$ and $B\cap
D=\varnothing$; or $\\{\gamma_{2}\\}\cup D=\\{\alpha_{2}\\}\cup B$. As
$|\alpha_{1}^{\langle x\rangle}|\geqslant 3$, we can repeat the argument with
$\alpha_{2}$ replaced by an element of $\alpha_{1}^{\langle
x\rangle}\setminus\\{\alpha_{1},\alpha_{2}\\}$ to obtain $[a,b]\neq 1$. Since
$\langle a,b\rangle$ is dihedral, $(x,a,b,y)$ is a path in $\Xi(G)$ and
$d(x,y)\leqslant 3$.

Case (b): $\langle x\rangle$ and $\langle y\rangle$ each have at least three
orbits on $\Omega$. By Lemma 3.3, $x\sim a:=(\alpha_{1},\alpha_{2},\beta_{1})$
and $y\sim b:=(\alpha_{1},\gamma_{2},\delta_{1})$. Observe that
$t:={\mathrm{supp}(a)\cup\mathrm{supp}(b)}\leqslant 5<n$, and so $\langle
a,b\rangle<G$. Hence if $[a,b]\neq 1$, then $(x,a,b,y)$ is a path in $\Xi(G)$,
and so $d(x,y)\leqslant 3$. If instead $[a,b]=1$, then $t=3$ and
$b\in\\{a,a^{-1}\\}$, hence $a\sim y$ and $d(x,y)\leqslant 2$.

Case (c): Exactly one of $\langle x\rangle$ and $\langle y\rangle$ has exactly
two orbits on $\Omega$. We may assume that $\langle x\rangle$ has exactly two
orbits on $\Omega$. Lemma 3.3 shows that $x\sim
a:=(\alpha_{1},\alpha_{2})(\beta_{1},\beta_{2})$ and $y\sim
b:=(\alpha_{1},\gamma_{2},\delta_{1})$. Observe that $[a,b]\neq 1$ and
$\langle a,b\rangle$ is intransitive. Hence $a\sim b$ and $d(x,y)\leqslant 3$.
∎

###### Proof of Theorem 3.1.

Lemma 3.4 shows that $\Xi(G)$ is connected with diameter at most $4$.
Furthermore, if $n$ is even, then each derangement of $G$ generates a subgroup
with at least two orbits on $\Omega$. Hence Lemmas 3.4 and 3.5 yield
$\mathrm{diam}(\Xi(G))\leqslant 3$. ∎

Magma calculations show that $\mathrm{diam}(\Xi(A_{n}))=2$ whenever
$5\leqslant n\leqslant 10$. We do not know if there exists $n>10$ such that
$\mathrm{diam}(\Xi(A_{n}))>2$; see Question 1.6.

###  3.2. Sporadic groups

Let $G$ be a sporadic finite simple group, or the Tits group
${}^{2}F_{4}(2)^{\prime}$. In this subsection, we implicitly use [12, 37] to
determine information about maximal subgroups, conjugacy classes and
centralisers in $G$. Note that all maximal subgroups of $G$ are known, except
possibly when $G$ is the monster group, in which case any unknown maximal
subgroup has a non-abelian simple socle [37, p. 65].

######  Theorem 3.6.

The graph $\Xi(G)$ of the sporadic group or Tits group $G$ is connected with
diameter at most $4$. If
$G\in\\{\mathrm{M}_{11},\mathrm{M}_{12},\mathrm{M}_{22},\mathrm{M}_{23},\mathrm{J}_{1},\mathrm{J}_{2},\mathbb{B}\\}$,
then $\mathrm{diam}(\Xi(G))$ is given in Table 1.

######  Proposition 3.7.

Each maximal subgroup of $G$ has a centre of order at most $2$.

###### Proof.

Let $M$ be a maximal subgroup of $G$. If $M$ has a non-abelian simple socle,
then clearly $Z(M)=1$. Otherwise, we can use GAP [19] to verify that
$|Z(M)|\leqslant 2$. ∎

In light of Lemma 2.6, it will be useful to determine neighbours of
involutions in $\Xi(G)$.

######  Proposition 3.8.

Let $x$ be an element of $G$ of order at least $3$, and suppose that $x$ lies
in a maximal subgroup of $G$ of even order. Then $x$ is adjacent in $\Xi(G)$
to some involution of $G$.

###### Proof.

It suffices to show that there exists a maximal subgroup of $G$ that contains
both $x$ and an involution that does not centralise $x$. Let $M$ be a maximal
subgroup of $G$ of even order, with $x\in M$. Since $|x|>2$, Proposition 3.7
shows that $x\notin Z(M)$. Let $T_{M}$ be the set of involutions of $M$. If
$|T_{M}|>C_{M}(x)$, or if $\langle
T_{M}\rangle\mathrel{\mathchoice{\ooalign{\raisebox{1.06805pt}{$\displaystyle\lhd$}\cr$\displaystyle\leqslant$\cr}}{\ooalign{\raisebox{1.06805pt}{$\textstyle\lhd$}\cr$\textstyle\leqslant$\cr}}{\ooalign{\raisebox{0.60764pt}{$\scriptstyle\lhd$}\cr$\scriptstyle\leqslant$\cr}}{\ooalign{\raisebox{0.43402pt}{$\scriptscriptstyle\lhd$}\cr$\scriptscriptstyle\leqslant$\cr}}}M$
is equal to $M$, then $x$ does not centralise every involution of $M$. Note
that this second condition holds whenever $M$ is simple.

Using GAP, we see that if $x$ does not lie in any simple maximal subgroups,
nor in any maximal subgroups $M$ with $|T_{M}|>C_{M}(g)$, then one of the
following holds:

  1. (i)

$G=\mathrm{J}_{1}$ and $|x|\in\\{7,19\\}$;

  2. (ii)

$G=\mathrm{Ly}$ and $|x|\in\\{37,67\\}$;

  3. (iii)

$G=\mathrm{Co}_{1}$ and $|x|=3$;

  4. (iv)

$G=\mathrm{J}_{4}$ and $|x|\in\\{29,43\\}$;

  5. (v)

$G=\mathrm{Fi}_{24}^{\prime}$ and $|x|=29$;

  6. (vi)

$G=\mathbb{M}$ and $|x|=41$.

In case (iii), $x$ is an element of the $G$-conjugacy class labelled
$3\mathrm{A}$ in the Atlas [12], and lies in a maximal subgroup
$K\cong(A_{5}\times\mathrm{J}_{2})\mkern 1.5mu{:}\mkern 1.5mu2$, which clearly
satisfies $\langle T_{K}\rangle=K$. In all other cases, $|x|$ is odd and
$C_{G}(x)=x$, hence $x$ does not commute with any involution of $M$. ∎

######  Lemma 3.9.

Suppose that $G=\mathbb{B}$, and let $R$ and $M$ be maximal subgroups of $G$
isomorphic to $\mathrm{Fi}_{23}$. Additionally, let $s\in R$ with $|s|=23$.
Then there exists $f\in R\cap M$ such that $d(s,f)\leqslant 1$.

###### Proof.

Let $S:=\langle s\rangle$. If $S\leqslant M$, then we can set $f=s$.
Otherwise, $S\cap M=1$, and since $|R|\,|M|>|G|$, there exists $f\in(M\cap
R)\setminus\\{1\\}$. As $f\notin S=C_{R}(s)$, we observe that $s\sim f$. ∎

######  Lemma 3.10.

Suppose that $G=\mathbb{B}$, and let $s,y\in G\setminus\\{1\\}$, with
$|s|=23$. Then $d(s,y)\leqslant 3$.

###### Proof.

The element $s$ generates a Sylow $23$-subgroup $S$ of $G$ and lies in maximal
subgroups $R\cong\mathrm{Fi}_{23}$ and $T\cong
2^{1+22}\raisebox{2.58334pt}{$\cdot$}\mathrm{Co}_{2}$. Each maximal subgroup
of $G$ that contains $s$ and is not $G$-conjugate to $R$ or $T$ has shape
$47\mkern 1.5mu{:}\mkern 1.5mu23$. Moreover, $C_{R}(s)=S$ and (using
Proposition 3.7 and the Atlas) $C_{G}(s)=C_{T}(s)=Z(T)\times S\cong
C_{2}\times S$. In addition, Proposition 2.3 shows that $y\in L\setminus Z(L)$
for some maximal subgroup $L$ of $G$. We will show that $d(s,y)\leqslant 3$
whenever $L$ satisfies certain properties, and that we may often choose $L$ to
satisfy those properties.

Suppose first that $Z(L)>1$ and $|L|\,|T|>|G|$, so that $L\cap T\neq 1$. We
may assume that $L\neq T$, else $d(s,y)\leqslant 2$ by Lemma 2.1. If there
exists a non-identity $u\in(L\cap T)\cup Z(L)\cup Z(T)$, then $Z(L)\cup
Z(T)\subseteq L\cap T$ (otherwise, $u$ would be centralised by $L$ and an
element of $T\setminus L$, or by $T$ and an element of $L\setminus T$, and
hence by $G$). As $Z(L)\cap Z(T)=1$, we deduce that $Z(L)\cup Z(T)$ is a
proper subset of $\langle Z(L),Z(T)\rangle$. Thus, in general, $L\cap T$
contains an element $c\notin Z(L)\cup Z(T)$. Moreover, any such $c$ satisfies
$d(c,y)\leqslant 2$ by Lemma 2.1. In particular, if $S\leqslant L\cap T$, then
we can set $c=s$, and so $d(s,y)\leqslant 2$. Assume therefore that
$S\not\leqslant L\cap T$. We claim that $s\sim c$. Indeed, if $s\nsim c$, then
$c$ centralises $s$, and hence lies in $(Z(T)\times S)\setminus(Z(T)\cup S)$.
Thus $c=zs^{i}$ for some $i\in\\{1,2,\ldots,22\\}$, where $z$ is the unique
involution of $Z(T)$. This implies that $\langle c^{2}\rangle=\langle
s^{2i}\rangle=S$, and so $S\leqslant L\cap T$, a contradiction. Therefore,
$s\sim c$ and $d(s,y)\leqslant 3$.

Next, suppose that $Z(L)=1$, $|L|\,|R|>|G|$, and $L\not\cong R$. Then $L\cap
R\neq 1$, while $S\cap L=1$ (since no $L$ satisfying the given assumptions has
order divisible by $|S|$). As $C_{R}(s)=S$, each $b\in L\cap R$ is adjacent to
$s$ in $\Xi(G)$. Moreover, $d(b,y)\leqslant 2$ by Lemma 2.1, and so again
$d(s,y)\leqslant 3$.

Assume now that $|y|\notin\\{25,47,55\\}$. Using GAP, we see that there exists
a maximal subgroup $K$ of $G$ containing $y$, such that either $Z(K)>1$ and
$|K|\,|T|>|G|$; or $Z(K)=1$, $|K|\,|R|>|G|$, and $K\not\cong R$. Moreover,
Proposition 3.7 and Lemma 2.5(i) show that $K\setminus Z(K)$ contains a
$G$-conjugate of $y$. Hence we can choose $L$ to be a $G$-conjugate of $K$,
and $d(s,y)\leqslant 3$ by the previous two paragraphs. To complete the proof,
we will consider the remaining elements $y$.

Case (a): $|y|=47$. Here, $C_{G}(y)=\langle y\rangle$, and each maximal
subgroup of $G$ containing $y$ has shape $47\mkern 1.5mu{:}\mkern 1.5mu23$. As
$S$ is a Sylow subgroup of $G$, it follows that $y\sim s^{\prime}$ for some
$s^{\prime}\neq 1$ in a $G$-conjugate $S^{\prime}$ of $S$. To complete the
proof in this case, we will show that $d(s,s^{\prime})\leqslant 2$.

The element $s^{\prime}$ lies in a $G$-conjugate $M$ of $R$. If $\langle
s\rangle=\langle s^{\prime}\rangle$, then it is clear that
$d(s,s^{\prime})=2$. Otherwise, $[s,s^{\prime}]\neq 1$, and so if $s$ or
$s^{\prime}$ lies in $R\cap M$, then $d(s,s^{\prime})=1$. Suppose finally that
$s,s^{\prime}\notin R\cap M$. We deduce from Lemma 3.9 that
$d(s,f)=1=d(s^{\prime},f^{\prime})$ for some $f,f^{\prime}\in R\cap M$. Hence
there exists $t\in R\cap M$ centralising neither $s$ nor $s^{\prime}$, and
$(s,t,s^{\prime})$ is a path in $\Xi(G)$.

Case (b): $|y|\in\\{25,55\\}$. There is a unique $G$-conjugacy class of
elements of order $|y|$, and so we may choose $L\cong\mathrm{HN}\mkern
1.5mu{:}\mkern 1.5mu2$ if $|y|=25$, or $L\cong(5\mkern 1.5mu{:}\mkern
1.5mu4)\times(\mathrm{HS}\mkern 1.5mu{:}\mkern 1.5mu2)$ if $|y|=55$. In either
case, no involution of $G$ has a centraliser of order $|L|$, and so
Proposition 3.7 yields $Z(L)=1$.

First suppose that there exists $g\in(L\cap R)\setminus\\{1\\}$. Then
$g\notin{S\cup Z(L)\cup Z(R)}$, as $|S|$ does not divide $|L|$ and
$Z(L)=Z(R)=1$. Hence Lemma 2.1 yields $d(s,g),d(g,y)\leqslant 2$.
Additionally, $C_{G}(y)=\langle y\rangle$, and so $C_{G}(y)\cap C_{G}(s)=1$.
Thus either $s\sim g$ or $d(g,y)\leqslant 1$, and $d(s,y)\leqslant 3$.

Suppose finally that $L\cap R=1$. Each of $G$ and $R$ has a unique conjugacy
class of elements of order $35$, and $L$ also contains elements of order $35$.
Hence there exists a $G$-conjugate $M$ of $R$ such that $L\cap M$ contains an
element $m$ of order $35$, and $m\sim y$ since $C_{G}(y)=\langle y\rangle$.
Additionally, Lemma 3.9 shows that $d(s,f)\leqslant 1$ for some $f\in R\cap
M$. Note that $f\in M\setminus\langle m\rangle=M\setminus C_{M}(m)$, since
$m\in L$ and $L\cap R=1$. Thus $f\sim m$ and $d(s,y)\leqslant 3$. ∎

###### Proof of Theorem 3.6.

For each
$G\in\\{\mathrm{M}_{11},\mathrm{M}_{12},\mathrm{M}_{22},\mathrm{M}_{23},\mathrm{J}_{1},\mathrm{J}_{2}\\}$,
we obtain $\mathrm{diam}(\Xi(G))$ using Magma. In the remaining cases, for
$i\in\\{1,2\\}$, let $x_{i}$ be an element of $G\setminus\\{1\\}$ that lies in
a maximal subgroup $L_{i}$ of even order. By Proposition 3.8,
$d(x_{i},a_{i})\leqslant 1$ for some involution $a_{i}$ of $G$, and so we may
assume (using Proposition 2.3 when $|x_{i}|=2$) that $x_{i}\notin Z(L_{i})$.
Lemma 2.6 now gives $d(x_{1},x_{2})\leqslant 4$. Hence
$\mathrm{diam}(\Xi(G))\leqslant 4$ if each maximal subgroup of $G$ has even
order.

Since the intersection graph of $\mathbb{B}$ has diameter $5$ [17, Theorem
1.1], Lemma 2.4 yields $\mathrm{diam}(\Xi(\mathbb{B}))\geqslant 4$. To
complete the proof, it remains to show that $d(g,h)\leqslant 4$ whenever
$g,h\in G\setminus\\{1\\}$ and $h$ lies in no maximal subgroup of even order.
By Theorem 2.7, $G\in\\{\mathrm{Th},\mathbb{B}\\}$. Let $K$ be a maximal
subgroup of $G$ of odd order.

First assume that $G=\mathrm{Th}$. Then $K\cong 31\mkern 1.5mu{:}\mkern
1.5mu15$. Let $m\in K$. If $|m|=31$, then $m$ lies in a maximal subgroup of
$G$ of shape $2^{5}\raisebox{2.58334pt}{$\cdot$}\mathrm{L}_{5}(2)$, and
otherwise $|C_{G}(m)|$ is even. Thus each element of $G$ lies in a maximal
subgroup of even order, and so the element $h$ does not exist.

Suppose finally that $G=\mathbb{B}$. Then $K\cong 47\mkern 1.5mu{:}\mkern
1.5mu23$, $|h|=47$, and $C_{G}(h)=\langle h\rangle$. Thus $h\sim s$ for each
$s\in K$ of order $23$. As $d(s,g)\leqslant 3$ by Lemma 3.10, we conclude that
$d(h,g)\leqslant 4$. ∎

###  3.3. Exceptional groups of Lie type

We now prove the exceptional case of Theorem 1.1. In view of Proposition 1.5
and Theorem 2.7, it remains to prove the following.

######  Theorem 3.11.

Let $G$ be a finite simple group. If $G\cong\mathrm{Sz}(q)$, or if $q$ is odd
and $G\in\\{G_{2}(q),{}^{2}G_{2}(q),{}^{3}\\!D_{4}(q),F_{4}(q),E_{8}(q)\\}$,
then $\Xi(G)$ is connected with diameter at most $4$.

Given a group $X$, let $Q_{X}$ be the (characteristic) subgroup generated by
the involutions of $X$.

######  Lemma 3.12.

Let $S:=\mathrm{SL}(2,q)$, and let $H$ be a quasisimple group containing a
subgroup $K$, such that $K\cong S$ and $Z(H)=Z(K)$. Additionally, let $R$ be
the central product $S\circ H$, and let $\pi$ be the natural epimorphism
$S\times H\to R$. If $Q_{R}\neq R$, then $q=3$, $Q_{R}$ is a maximal subgroup
of $R$ that contains $(H)\pi$, and $C_{R}(Q_{R})=Z(R)$.

###### Proof.

We observe that $\tilde{S}:=(S)\pi$ and $\tilde{K}:=(K)\pi$ are normal
subgroups of $J:=S\circ K={(S\times K)\pi}$, and $\tilde{S}$ and
$\tilde{H}:=(H)\pi$ are normal subgroups of $R$, with $\tilde{S}\cong S$,
$\tilde{K}\cong K$ and $\tilde{H}\cong H$. Additionally,
$[\tilde{H},\tilde{S}]=([H,S])\pi=1$, and $\tilde{H}\tilde{S}=R$. Furthermore,
the centres of $R$, $J$, $\tilde{H}$, $\tilde{S}$ and $\tilde{K}$ all
coincide, and this common centre $\mathcal{Z}$ of order $(2,q-1)$ is equal to
$\tilde{H}\cap\tilde{S}$.

Now, $J\cong\Omega^{+}(4,q)$ [2, Lemma 1.12.3]. Suppose first that $q\neq 3$.
Then $Q_{J}=J$ by [27, Theorem 8.5]. Additionally, since
$\mathcal{Z}<\tilde{K}\leqslant\tilde{H}$, and since a quasisimple group’s
proper normal subgroups are precisely its central subgroups, no proper normal
subgroup of $\tilde{H}$ contains $\tilde{K}$. Hence no proper normal subgroup
of $R$ contains $J$. As $J=Q_{J}\leqslant
Q_{R}\mathrel{\mathchoice{\ooalign{\raisebox{1.06805pt}{$\displaystyle\lhd$}\cr$\displaystyle\leqslant$\cr}}{\ooalign{\raisebox{1.06805pt}{$\textstyle\lhd$}\cr$\textstyle\leqslant$\cr}}{\ooalign{\raisebox{0.60764pt}{$\scriptstyle\lhd$}\cr$\scriptstyle\leqslant$\cr}}{\ooalign{\raisebox{0.43402pt}{$\scriptscriptstyle\lhd$}\cr$\scriptscriptstyle\leqslant$\cr}}}R$,
we obtain $Q_{R}=R$.

Suppose from now on that $q=3$. We calculate that $\tilde{S}\cap Q_{J}$ is a
maximal subgroup of $\tilde{S}$, and that $\tilde{K}\cap Q_{J}>\mathcal{Z}$.
As the normal subgroup $\tilde{H}\cap Q_{R}$ of $\tilde{H}$ contains
$\tilde{K}\cap Q_{J}$, it follows that $\tilde{H}\leqslant Q_{R}$. Since
$R=\tilde{H}\tilde{S}$, we deduce that $Q_{R}=\tilde{H}\tilde{S}\cap
Q_{R}=\tilde{H}(\tilde{S}\cap Q_{R})$.

If $\tilde{S}\cap Q_{R}=\tilde{S}$, then $Q_{R}=R$. We will therefore assume
that $\tilde{S}\cap Q_{R}<\tilde{S}$. Then $\tilde{S}\cap Q_{R}$ is the
maximal subgroup $\tilde{S}\cap Q_{J}$ of $\tilde{S}$, and
$Q_{R}=\tilde{H}(\tilde{S}\cap Q_{J})$, which is maximal in
$\tilde{H}\tilde{S}=R$. Since $[\tilde{H},\tilde{S}]=1$, we obtain
$\mathcal{Z}\leqslant
C_{R}(Q_{R})=C_{\tilde{H}\tilde{S}}(\tilde{H}(\tilde{S}\cap Q_{J}))\leqslant
Z(\tilde{H})C_{\tilde{S}}(\tilde{S}\cap Q_{J}).$ We calculate that
$C_{\tilde{S}}(\tilde{S}\cap Q_{J})$ is equal to
$\mathcal{Z}=Z(\tilde{H})=Z(R)$, and hence so is $C_{R}(Q_{R})$. ∎

######  Proposition 3.13.

Let $H$ be a finite quasisimple group. If $|Z(H)|=2$, then assume that
$H/Z(H)$ is not isomorphic to $A_{7}$, or to $\mathrm{PSL}(2,q)$ for any odd
$q$. Then $Q_{H}=H$.

###### Proof.

The set $H\setminus Z(H)$ contains an involution, by [22] if $|Z(H)|$ is even,
and otherwise, since $|H|$ is even. Each proper normal subgroup of $H$ lies in
$Z(H)$, and so $Q_{H}=H$. ∎

######  Lemma 3.14.

Let $G\in\\{G_{2}(q),{}^{2}G_{2}(q),{}^{3}\\!D_{4}(q),F_{4}(q),E_{8}(q)\\}$
with $q$ odd, let $a$ be an involution of $G$, and let $Y:=C_{G}(a)$. Then
$C_{Y}(Q_{Y})=Z(Y)=\langle a\rangle$.

###### Proof.

We observe from [21, pp. 171–177] that $Z(Y)=\langle a\rangle$, and either:

  1. (a)

$G\cong{}^{2}G_{2}(q)$ and $Y\cong C_{2}\times\mathrm{PSL}(2,q)$;

  2. (b)

$G\cong F_{4}(q)$ and $Y\cong\mathrm{Spin}(9,q)$;

  3. (c)

$G\cong E_{8}(q)$ and $Y\cong J\mkern 1.5mu{:}\mkern 1.5mu2$, where
$J:=(\mathrm{Spin}^{+}(16,q)/A)$, and $A$ is a central subgroup of
$\mathrm{Spin}^{+}(16,q)$ of order $2$; or

  4. (d)

$Y=R\mkern 1.5mu{:}\mkern 1.5muA$, with $|A|=2$ and
$R\cong\mathrm{SL}(2,q)\circ H$, where $(G,H)$ lies in the set

$\\{(G_{2}(q),\mathrm{SL}(2,q)),({}^{3}\\!D_{4}(q),\mathrm{SL}(2,q^{3})),(F_{4}(q),\mathrm{Sp}(6,q)),(E_{8}(q),E_{7}(q)_{\mathrm{sc}})\\}.$

Additionally, $Z(Y)=Z(R)$, and $A$ induces an outer automorphism on the image
of $H$ under the natural epimorphism $\pi:\mathrm{SL}(2,q)\times H\to R$.

We will divide the remainder of the proof into the cases above. In each case,
since $Z(Y)=\langle a\rangle$, it remains to show that $C_{Y}(Q_{Y})=Z(Y)$.
Note that this is certainly the case if $Q_{Y}=Y$.

Cases (a)–(c). By applying Proposition 3.13 to $Y$ in Case (b) and $J$ in Case
(c), we easily deduce that $Q_{Y}=Y$ in each case.

Case (d). If $G\cong G_{2}(3)$, then $Y\cong\mathrm{SO}^{+}(4,3)$ [36, p.
125], and $Q_{Y}=Y$. Suppose therefore that $G\not\cong G_{2}(3)$, and that
$Q_{Y}<Y$. Notice that $Q_{Y}$ contains $\langle Q_{R},A\rangle=Q_{R}\mkern
1.5mu{:}\mkern 1.5muA$, and thus $Q_{R}<R$.

In order to apply Lemma 3.12, we will show that the quasisimple group $H$
contains a subgroup $K$ such that $K\cong\mathrm{SL}(2,q)$ and $Z(H)=Z(K)$.
Such $K$ clearly exists if there exists $L\leqslant H$ with $Z(H)=Z(L)$ and
$L\cong\mathrm{SL}(2,q^{i})$ for some positive integer $i$. Hence this is the
case if $H\in\\{\mathrm{SL}(2,q),\mathrm{SL}(2,q^{3})\\}$. If instead
$H=E_{7}(q)_{\mathrm{sc}}$, then $H$ contains a subgroup
$L\cong\mathrm{SL}(2,q^{7})$, with $Z(H)=Z(L)$ [23, p. 927]. Finally, if
$H=\mathrm{Sp}(6,q)$, then let $V_{1}$, $V_{2}$ and $V_{3}$ be non-degenerate
two-dimensional subspaces of the symplectic space $V:=\mathbb{F}_{q}^{6}$,
such that $V_{2}\oplus V_{3}=V_{1}^{\perp}$ (with respect to $V$) and
$V_{3}=V_{2}^{\perp}$ (with respect to $V_{2}\oplus V_{3}$). Then the
intersection of the stabilisers in $H$ of $V_{1}$, $V_{2}$ and $V_{3}$ is
isomorphic to $\mathrm{Sp}(2,q)^{3}=\mathrm{SL}(2,q)^{3}$. The diagonal
subgroup of this direct product is isomorphic to $\mathrm{SL}(2,q)$ and has
centre $Z(H)$.

Lemma 3.12 now shows that $Q_{R}$ is a maximal subgroup of $R$, that
$(H)\pi\leqslant Q_{R}$, and that $C_{R}(Q_{R})=Z(R)$. It follows from this
first fact that the proper subgroup $Q_{Y}$ of $Y$ is maximal and equal to
$Q_{R}\mkern 1.5mu{:}\mkern 1.5muA$. Since $(H)\pi\leqslant Q_{R}\leqslant
R=(\mathrm{SL}(2,q))\pi(H)\pi$ and $[(\mathrm{SL}(2,q))\pi,(H)\pi]=1$, the
outer automorphism of $(H)\pi$ induced by $A$ does not extend to an inner
automorphism of $Q_{R}$. Therefore, $C_{Y}(Q_{R})=C_{R}(Q_{R})=Z(R)$, which is
equal to $Z(Y)$ from the start of the proof. As $Z(Y)\leqslant
C_{Y}(Q_{Y})\leqslant C_{Y}(Q_{R})$, we conclude that $C_{Y}(Q_{Y})=Z(Y)$. ∎

The finite simple groups in the statement of the above lemma are those whose
involutions are all centralised by maximal subgroups of _maximal rank_ (see
[21, Theorem 4.5.1] and [30]).

###### Proof of Theorem 3.11.

Theorem 2.7 implies that each maximal subgroup of $G$ has even order, and so
it suffices by Proposition 2.3 and Lemma 2.6 to show that each non-involution
$x\in G\setminus\\{1\\}$ is adjacent in $\Xi(G)$ to some involution. Let $M$
be a maximal subgroup of $G$ containing $x$. Assume first that
$G\not\cong\mathrm{Sz}(q)$, so that $q$ is odd, and let $a$ be an involution
of $M$. If $x\sim a$, then we are done. Otherwise, $x\in C_{G}(a)$. By Lemma
3.14, $a$ is the unique non-identity element of $C_{G}(a)$ that centralises
each involution of $C_{G}(a)$. Hence $x\sim a^{\prime}$ for some involution
$a^{\prime}\in C_{G}(a)$.

Assume now that $G\cong\mathrm{Sz}(q)$. Then $Z(M)=1$ by [35, Theorem 4] and
[33, p. 183], and so $C_{M}(x)<M$. If $M\cong\mathrm{Sz}(q_{0})$, for some
proper power $q_{0}$ of $2$ dividing $q$, then $M=Q_{M}$. It follows in this
case that $M$ contains an involution $a$ not centralising $x$, and so $x\sim
a$. If instead $M\not\cong\mathrm{Sz}(q_{0})$, then by [35, §4, p. 133, &
Theorem 9], $M$ is conjugate in $G$ to either:

  1. (a)

the Frobenius group $W:=S\mkern 1.5mu{:}\mkern 1.5muC_{q-1}$, where $S$ is a
Sylow $2$-subgroup of $G$;

  2. (b)

the dihedral group $X:=D_{2(q-1)}$; or

  3. (c)

a Frobenius group $Y_{\pm}:=C_{q\pm\sqrt{2q}+1}\mkern 1.5mu{:}\mkern
1.5muC_{4}$.

If $M\cong X$, then again $Q_{M}=M$ and $x\sim a$ for some involution $a\in
M$. If instead $M\cong Y_{\pm}$, then let $N$ be the normal subgroup
$C_{q\pm\sqrt{2q}+1}$ of $M$. As $M$ is Frobenius, there exists a complement
$H$ of $N$ with $x\notin H$. No non-identity element of $H$ centralises $x$,
and so $x$ is adjacent in $\Xi(G)$ to the unique involution of $H$.

Suppose finally that $M\cong W$. If $x\notin S$, then $x$ centralises no non-
identity element of $S$, and so $x$ is adjacent in $\Xi(G)$ to each involution
of $S$. Now, $Z(S)$ consists of all elements of $S$ of order at most $2$, and
each element of $S\setminus Z(S)$ has order $4$ [35, Lemma 1 & Theorem 7].
Additionally, $G$ has a unique conjugacy class of cyclic subgroups of order
$4$ (see [35, p. 121 & Proposition 18]), and so if the non-involution $x$ lies
in $S$, then it also lies in a maximal subgroup $L\cong Y_{\pm}$. By the
previous paragraph, $x$ is adjacent in $\Xi(G)$ to an involution of $L$. ∎

Magma calculations show that $\mathrm{diam}(\Xi(\mathrm{Sz}(8)))=3$ and
$\mathrm{diam}(\Xi(G_{2}(3)))=2$. We do not know if any finite simple
exceptional group $G$ satisfies $\mathrm{diam}(\Xi(G))>3$.

##  4\. Matrices and subspace stabilisers

We now explore various matrices and subspace stabilisers. The results here
will be useful when proving Theorem 1.1 for linear and unitary groups. Let $n$
be a positive integer, $q$ a prime power, and $I_{k}$ the $k\times k$ identity
matrix over $\mathbb{F}_{q}$, for a positive integer $k$. Additionally, let
$E_{i,j}$ be the $n\times n$ matrix with $(i,j)$ entry equal to $1$ and all
other entries equal to $0$.

###  4.1. Matrices and subspace stabilisers in linear groups

######  Definition 4.1 ([32, p. 148 & pp. 161–162]).

Let $f(x):=x^{n}-\beta_{n}x^{n-1}-\ldots-\beta_{2}x-\beta_{1}$ be a (monic)
polynomial in $\mathbb{F}_{q}[x]$. The _companion matrix_ of $f$ is the
$n\times n$ matrix

$C(f):=\left(\begin{matrix}0&I_{n-1}\\\ A&B\end{matrix}\right),$

where $A:=(\begin{matrix}\beta_{1}\end{matrix})$,
$B:=(\begin{matrix}\beta_{2}&\cdots&\beta_{n}\end{matrix})$, and $C(f)=A$ when
$n=1$. If $f$ is irreducible over $\mathbb{F}_{q}$, then for each positive
integer $k$, the _hypercompanion matrix_ of $f^{k}$ is the $kn\times kn$
matrix

$C_{k}(f):=\left(\begin{matrix}C(f)&E_{n,1}&0&\cdots&0\\\
0&C(f)&E_{n,1}&\cdots&0\\\ \vdots&\vdots&\ddots&\ddots&\vdots\\\
0&0&0&\ddots&E_{n,1}\\\ 0&0&0&\cdots&C(f)\end{matrix}\right).$

Since a subgroup $\langle A\rangle$ of $\mathrm{GL}(n,q)$ is irreducible if
and only if the characteristic polynomial $\chi_{A}$ of $A$ is irreducible,
the following lemma will shed light on certain irreducible subgroups.

######  Lemma 4.2.

Let $a\in\mathbb{F}_{q}^{\times}$. Then the set of irreducible factors in
$\mathbb{F}_{q}[x]$ of the binomial $x^{q-1}-a$ is $\\{x^{|a|}-b\mid
b\in\mathbb{F}_{q}^{\times},b^{(q-1)/|a|}=a\\}$.

###### Proof.

For each positive integer $k$, let $\phi_{k}$ be the homomorphism $s\mapsto
s^{k}$ of $\mathbb{F}_{q}^{\times}$, and let $H_{k}$ be the image of
$\phi_{k}$, of order $(q-1)/(k,q-1)$. Additionally, let $r:=|a|$ and
$t:=(q-1)/r$. Then $H_{t}=\langle a\rangle$. Since $|\ker(\phi_{t})|=t$, there
are exactly $t$ distinct roots $b_{1},\ldots,b_{t}\in\mathbb{F}_{q}^{\times}$
of the binomial $f(x):=x^{t}-a$. Hence $f(x)=\prod_{i=1}^{t}(x^{t}-b_{i})$,
and $x^{q-1}-a=f(x^{r})=\prod_{i=1}^{t}(x^{r}-b_{i}).$

It remains to show that the binomial $x^{r}-b_{i}$ is irreducible over
$\mathbb{F}_{q}$ for each $i$. Since $b_{i}^{t}=a$, we see that $r=|a|$
divides $|b_{i}|$. Additionally, if $r$ is divisible by $4$, then so is $q-1$.
It therefore suffices by [28, Theorems 3.3 & 3.35] to prove that $r$ is
coprime to $u:=(q-1)/|b_{i}|$.

Since $|H_{u}|=|b_{i}|$, there exists $c_{i}\in\mathbb{F}_{q}^{\times}$ with
$c_{i}^{u}=b_{i}$, and hence $c_{i}^{ut}=a$. Thus $a\in H_{ut}$, and so $r$
divides $|H_{ut}|={(q-1)/(ut,q-1)}=tr/(ut,tr)=r/(u,r)$. Hence $(u,r)=1$. ∎

######  Lemma 4.3.

Let $A\in\mathrm{GL}(n,q)$. Suppose also that $A^{q-1}\in
Z(\mathrm{GL}(n,q))$, and that $\langle A\rangle$ acts irreducibly on
$\mathbb{F}_{q}^{n}$. Then $A$ is similar to the companion matrix
$C(x^{n}-b)$, for some $b\in\mathbb{F}_{q}^{\times}$ such that $x^{n}-b$ is
irreducible over $\mathbb{F}_{q}$.

###### Proof.

Since $A^{q-1}\in Z(\mathrm{GL}(n,q))$, there exists
$a\in\mathbb{F}_{q}^{\times}$ such that $A^{q-1}-aI_{n}=0$. Hence
$x^{q-1}-a\in\mathbb{F}_{q}[x]$ is divisible by $\chi_{A}$, which is
irreducible over $\mathbb{F}_{q}$. It now follows from Lemma 4.2 that
$\chi_{A}(x)=x^{n}-b$ for some $b\in\mathbb{F}_{q}^{\times}$. Hence $A$ is
similar to $C(x^{n}-b)$. ∎

######  Lemma 4.4.

Let $A\in\mathrm{SL}(n,q)$. Suppose also that $A^{q^{2}-1}\in
Z(\mathrm{SL}(n,q))$, and that $\langle A\rangle$ acts irreducibly on
$\mathbb{F}_{q}^{n}$. Then $n\in\\{1,2\\}$.

###### Proof.

Since $A^{q^{2}-1}\in Z(\mathrm{SL}(n,q))$, there exists
$a\in\mathbb{F}_{q}^{\times}$ such that $A^{q^{2}-1}-aI_{n}=0$. Thus
$\chi_{A}$, which is irreducible over $\mathbb{F}_{q}$, divides
$x^{q^{2}-1}-a\in\mathbb{F}_{q}[x]$. Furthermore, $\mathbb{F}_{q^{n}}$ is the
splitting field for $\chi_{A}$ over $\mathbb{F}_{q}$, and $A$ is similar to
$C(\chi_{A})$. To prove the required result, we will study $\chi_{A}$ as a
polynomial in $\mathbb{F}_{q^{2}}[x]$. By Lemma 4.2, the set of irreducible
factors in $\mathbb{F}_{q^{2}}[x]$ of $x^{q^{2}-1}-a$ is $\\{x^{|a|}-b\mid
b\in\mathbb{F}_{q^{2}}^{\times},b^{(q^{2}-1)/|a|}=a\\}$.

If $n$ is odd, then $\chi_{A}$ is irreducible over $\mathbb{F}_{q^{2}}$. Thus
$n=|a|$, and $\chi_{A}=x^{n}-b$ for some $b\in\mathbb{F}_{q}^{\times}$ with
$b^{(q^{2}-1)/n}=a$. Since $\det(C(x^{n}-b))=b$, we deduce that $b=1$. Hence
$a=1$ and $n=1$.

If instead $n$ is even, then each irreducible factor of $\chi_{A}$ in
$\mathbb{F}_{q^{2}}$ has degree $n/2$. In particular, $|a|=n/2$, and there
exist $b_{1},b_{2}\in\mathbb{F}_{q^{2}}^{\times}$ such that

$\chi_{A}=(x^{n/2}-b_{1})(x^{n/2}-b_{2})={x^{n}-(b_{1}+b_{2})x^{n/2}+b_{1}b_{2}},$

with $b_{1}^{(q^{2}-1)/(n/2)}=b_{2}^{(q^{2}-1)/(n/2)}=a$ and
$b_{1}b_{2},b_{1}+b_{2}\in\mathbb{F}_{q}$. Here,
$\det(C(\chi_{A}))=b_{1}b_{2}$, and thus $b_{2}=b_{1}^{-1}$. Therefore,
$a=a^{-1}$, and hence $n/2=|a|\in\\{1,2\\}$. In particular, if $q$ is even,
then $a\in\mathbb{F}_{q}^{\times}$ has odd order, and $n=2$. Otherwise,
arguing as in [11, pp. 569–570] shows that the irreducible polynomial
$x^{n}-(b_{1}+b_{2})x^{n/2}+1\in\mathbb{F}_{q}[x]$ cannot have degree $4$, and
again $n=2$. ∎

Let $H:=\mathrm{SL}(n,q)$, with $n\geqslant 2$, and $q\geqslant 4$ if $n=2$,
so that $H/Z(H)$ is simple. Additionally, let $V:=\mathbb{F}_{q}^{n}$ be the
natural module for $H$, and $H_{X}$ the stabiliser in $H$ of a subspace $X$ of
$V$.

######  Lemma 4.5.

Let $X$ and $Y$ be distinct one-dimensional subspaces of $V$. Then:

  1. (i)

no commutator in $H_{X}$ is a non-identity scalar matrix;

  2. (ii)

$C_{H}(H_{X})=Z(H)$; and

  3. (iii)

$C_{H}(H_{X}\cap H_{Y})=\begin{cases}H_{X}\cap H_{Y},&\text{ if }n=2,\text{ or
}n=3\text{ and }q=2,\\\ Z(H),&\text{ otherwise.}\end{cases}$

###### Proof.

Up to conjugacy by a fixed element of $H$, the stabiliser $H_{X}$ consists of
the matrices in $H$ with a first row of the form
$\begin{matrix}(\lambda_{1}&0&0&\cdots&0)\end{matrix}$, with
$\lambda_{1}\in\mathbb{F}_{q}^{\times}$, and $H_{Y}$ is the set of matrices
with a second row of the form
$\begin{matrix}(0&\lambda_{2}&0&\cdots&0)\end{matrix}$, with
$\lambda_{2}\in\mathbb{F}_{q}^{\times}$. For each $T,U\in H_{X}$, the $(1,1)$
entry of $[T,U]$ is equal to $1$, and hence if $[T,U]\in Z(H)$, then
$[T,U]=1$. Thus (i) holds. We split the proof of (ii)–(iii) into two cases. In
each case, let $W\in C_{H}(H_{X}\cap H_{Y})$.

Case (a): $n=2$. Let $\omega$ be a primitive element of $\mathbb{F}_{q}$,
$A:=\mathrm{diag}(\omega,\omega^{-1})\in H_{X}\cap H_{Y}$, and
$D:=I_{2}+E_{2,1}\in H_{X}$. The equality $AW=WA$ gives $W\in H_{X}\cap
H_{Y}$, which is abelian. Hence we obtain (iii). If $W\in C_{H}(X)$, then
$DW=WD$, and we deduce that $W\in Z(H)$, hence (ii).

Case (b): $n\geqslant 3$. It is easy to check the result if $n=3$ and $q=2$,
so assume otherwise. If $n=3$, then let
$b\in\mathbb{F}_{q}^{\times}\setminus\\{1\\}$ and
$B:=\mathrm{diag}(1,b,b^{-1}),B^{\prime}:=\mathrm{diag}(b,1,b^{-1})\in
H_{X}\cap H_{Y}$. We deduce from the equalities $BW=WB$ and
$B^{\prime}W=WB^{\prime}$ that $W$ is diagonal. If instead $n\geqslant 4$,
then let $r$ and $s$ be distinct integers with $3\leqslant r\leqslant n$ and
$1\leqslant s\leqslant n$. Then $C_{r,s}:=I_{n}+E_{r,s}\leqslant H_{X}\cap
H_{Y}$, and the equalities $C_{r,s}W=WC_{r,s}$ (for all $r$ and $s$) imply
that $W$ is again diagonal.

In each case, let $F:=I_{n}+\sum_{j=1}^{n-1}E_{n,j}\in H_{X}\cap H_{Y}$. As
$W$ is diagonal, the equality $WF=FW$ yields $W\in Z(H)$. Thus we have proved
(iii), and (ii) follows immediately. ∎

###  4.2. Subspace stabilisers in unitary groups

Throughout this subsection, let $n\geqslant 3$, with $q\geqslant 3$ if $n=3$,
so that $G:=\mathrm{PSU}(n,q)$ is simple. Additionally, let $V$ be the natural
module $\mathbb{F}_{\\!q^{2}}^{n}$ for $\mathrm{SU}(n,q)$, equipped with the
unitary form with Gram matrix $I_{n}$. Then a matrix
$A\in\mathrm{SL}(n,q^{2})$ lies in $\mathrm{SU}(n,q)$ if and only if
$AA^{\sigma T}=I_{n}$, where $\sigma$ is the automorphism
$\alpha\mapsto\alpha^{q}$ of $\mathbb{F}_{\\!q^{2}}$. The following theorem
will be useful when considering $\Xi(G)$. Here, $G_{(\Delta)}$ denotes the
pointwise stabiliser in $G$ of a set $\Delta$ of subspaces of $V$.

######  Theorem 4.6.

Let $\Delta$ be a set of $k$-dimensional subspaces of $V$.

  1. (i)

Suppose that $|\Delta|<\lceil n/k\rceil$. If $(q+1)\nmid n$, or if
$k\nmid(n-1)$, then $G_{(\Delta)}\neq 1$.

  2. (ii)

Suppose that $|\Delta|<\lceil n/k\rceil-1$. Then $G_{(\Delta)}\neq 1$.

An analogue of the following lemma holds for certain classical algebraic
groups; see [7, §4.1].

######  Lemma 4.7.

Let $W$ be an $(n-1)$-dimensional subspace of $V$. Then $\mathrm{SU}(n,q)$
contains a non-scalar matrix that acts as a scalar on $W$ if and only if
$W^{\perp}$ is totally singular or $(q+1)\nmid n$.

###### Proof.

First, $\mathrm{SU}(n,q)$ has two orbits on the set of one-dimensional
subspaces of $V$: the non-degenerate subspaces, and the totally singular
subspaces (see [6, Remark 4.1.2]). Thus it suffices to consider two choices
for $W$, one for each possible orbit containing $W^{\perp}$. Let
$\\{e_{1},\ldots,e_{n}\\}$ be the basis for $V$ corresponding to the Gram
matrix $I_{n}$, and let $\omega$ be a primitive element of
$\mathbb{F}_{\\!q^{2}}$.

Case (a): $W^{\perp}$ is non-degenerate. We may assume that $W^{\perp}=\langle
e_{1}\rangle$, so that $W=\langle e_{2},e_{3},\ldots,e_{n}\rangle$. Any matrix
in $\mathrm{SL}(n,q^{2})$ that acts as a scalar on $W$ also stabilises
$W^{\perp}$, and hence is equal to
$B_{\alpha}:=\mathrm{diag}(\alpha^{-(n-1)},\alpha,\ldots,\alpha)$ for some
$\alpha\in\mathbb{F}_{\\!q^{2}}^{\times}$. Moreover,
$B_{\alpha}\in\mathrm{SU}(n,q)$ if and only if $\alpha^{q+1}=1$.

Let $\lambda:=\omega^{q-1}$. Observe that if $(q+1)\nmid n$, then
$B_{\lambda}$ is a non-scalar matrix in $\mathrm{SU}(n,q)$ that acts as
$\lambda$ on $W$. If instead $q+1\mid n$, then any scalar
$\alpha\in\mathbb{F}_{\\!q^{2}}^{\times}$ satisfying $\alpha^{q+1}=1$ also
satisfies $(\alpha^{n-1})^{-1}=\alpha$. Therefore, in this case, no non-scalar
matrix in $\mathrm{SU}(n,q)$ acts as a scalar on $W$.

Case (b): $W^{\perp}$ is totally singular. If $q$ is even, then let
$\gamma:=\omega^{q+1}$ and $\delta:=1$, and otherwise, let $\gamma:=\omega$
and $\delta:=\omega^{(q-1)/2}$. Then $\delta^{q+1}=-1$ for all $q$, and so
$\delta e_{1}+e_{2}$ is singular. Hence we may assume that
$W^{\perp}=\langle\delta e_{1}+e_{2}\rangle$, so that $W=\langle\delta
e_{1}+e_{2},e_{3},\ldots,e_{n}\rangle$. The direct sum of
$\left(\begin{matrix}1+\gamma\delta&\gamma\\\
-\gamma\delta^{2}&1-\gamma\delta\\\ \end{matrix}\right)$ and $I_{n-2}$ is a
non-scalar matrix in $\mathrm{SU}(n,q)$ that acts trivially on $W$. ∎

######  Corollary 4.8.

Let $U$ be an $(n-2)$-dimensional subspace of $V$. Then $\mathrm{SU}(n,q)$
contains a non-scalar matrix that acts as a scalar on $U$.

###### Proof.

Observe that $U^{\perp}$ contains a one-dimensional totally singular subspace
$X$. By Lemma 4.7, some non-scalar matrix in $\mathrm{SU}(n,q)$ acts as a
scalar on $X^{\perp}$, and hence on $U\subseteq X^{\perp}$. ∎

###### Proof of Theorem 4.6.

If $|\Delta|<\lceil n/k\rceil$, then the subspace $\langle\Delta\rangle$ of
$V$ lies in an $(n-1)$-dimensional subspace $W$. Lemma 4.7 shows that if
$(q+1)\nmid n$, then $\mathrm{SU}(n,q)$ contains a non-scalar matrix that acts
as a scalar on $W$, and hence on $\langle\Delta\rangle$. Therefore,
$G_{(\Delta)}\neq 1$.

Finally, assume that $|\Delta|<\lceil n/k\rceil-1$, or that $|\Delta|=\lceil
n/k\rceil-1$ and $k\nmid(n-1)$. Then $\langle\Delta\rangle$ lies in an
${(n-2)}$-dimensional subspace $U$ of $V$. By Corollary 4.8,
$\mathrm{SU}(n,q)$ contains a non-scalar matrix that acts as a scalar on $U$,
and hence on $\langle\Delta\rangle$. We again conclude that ${G_{(\Delta)}\neq
1}$. ∎

##  5\. Linear and unitary groups and the non-generating graph

In this section, we complete the proof of Theorem 1.1 by showing that it holds
for linear and unitary groups. In addition, we prove Theorem 1.8.

Let $n$, $q$, $I_{k}$ and $E_{i,j}$ be as in §4. Additionally, let
$H\in\\{\mathrm{SL}(n,q),\mathrm{SU}(n,q)\\}$, $Z:=Z(H)$, and $G:=H/Z$. We
will largely work in the group $H$ and appeal to Lemma 2.2, with $N=Z$. We
will also implicitly use the fact that $\Xi(H)$ is invariant under conjugation
by the elements of $H$.

###  5.1. Linear groups

Assume that $H=\mathrm{SL}(n,q)$, with $n\geqslant 2$, and $q\geqslant 4$ if
$n=2$, so that $G$ is simple.

######  Theorem 5.1.

Let $G$ be the linear group $\mathrm{PSL}(n,q)$. Then
$\mathrm{diam}(\Xi(G))\leqslant 4$.

######  Remark 5.2.

Let $J:=\mathrm{PGL}(n,q)$. A straightforward generalisation of the proofs in
this subsection shows that $\Xi(J)$ is connected. Thus when $J$ is not simple,
[16, Theorem 1.2] yields $\mathrm{diam}(\Xi(J))\leqslant 3$. We see using
Magma that this bound is achieved by $\mathrm{PGL}(2,7)$ and
$\mathrm{PGL}(3,4)$.

Let $\mathcal{U}$ be the set of one-dimensional subspaces of the natural
module $V:=\mathbb{F}_{q}^{n}$ for $H$. We proceed by exploring paths in
$\Xi(H)$ containing elements that stabilise subspaces in $\mathcal{U}$.

######  Lemma 5.3.

Let $X,Y\in\mathcal{U}$, $K\in H_{X}\setminus Z$, and $L\in H_{Y}\setminus Z$.
Then $d(ZK,ZL)\leqslant 2$.

###### Proof.

We may assume that $K\neq L$. We claim that there exists a path
$(U_{1},\ldots,U_{j})$ in $\Xi(H)$, where $j\leqslant 3$, $U_{1}=K$,
$U_{j}=L$, and $U_{2}\in H_{X}\cap H_{Y}$. Since $Z(H_{X})=Z(H_{Y})=Z$ by
Lemma 4.5(ii), the claim follows from Lemma 2.1 if $K$ or $L$ lies in
$H_{X}\cap H_{Y}$. Otherwise, Lemma 4.5(iii) implies that $C_{H_{X}\cap
H_{Y}}(K)$ and $C_{H_{X}\cap H_{Y}}(L)$ are proper subgroups of $H_{X}\cap
H_{Y}$. Thus there exists an $M\in H_{X}\cap H_{Y}$ centralising neither $K$
nor $L$, and we can set $U_{2}=M$.

Now, $[U_{i},U_{i+1}]\neq 1$ for all $i\in\\{1,\ldots,j-1\\}$, and so
$[U_{i},U_{i+1}]\notin Z$ by Lemma 4.5(i). Moreover, $\langle
U_{i},U_{i+1},Z\rangle$ lies in $H_{X}$ or $H_{Y}$. Hence by Lemma 2.2,
$(ZU_{1},\ldots,ZU_{j})$ is a path in $\Xi(G)$. ∎

######  Lemma 5.4.

Let $A\in H$ such that $\langle A\rangle$ acts reducibly on $V$, but does not
stabilise any subspace in $\mathcal{U}$. Then there exist $X\in\mathcal{U}$
and $B\in H_{X}$ such that $ZA\sim ZB$.

###### Proof.

The assumptions on $A$ imply that its characteristic polynomial $\chi_{A}$ is
reducible over $\mathbb{F}_{q}$ and has no linear factor in $\mathbb{F}_{q}$.
Hence $n>2$. We may assume without loss of generality (see [32, Theorem 8.10])
that $A$ is a block matrix whose final row of blocks is equal to
$\begin{matrix}(0&\cdots&0&R)\end{matrix}$, with $R$ a hypercompanion matrix
and a proper submatrix of $A$. Let $B:=I_{n}+E_{2,1}$. Then $B\in H_{X}$,
where $X\in\mathcal{U}$ is spanned by the vector
$\begin{matrix}(1&0&0&\cdots&0)\end{matrix}$. Each matrix in $Z\cup\\{B\\}$
can be viewed as a block matrix, with a final row of blocks equal to
$\begin{matrix}(0&\cdots&0&S)\end{matrix}$ for some nonzero block $S$ with
same dimensions as $R$. Hence $\langle A,B,Z\rangle<H$.

By Lemma 2.2, it remains to prove that $[ZA,ZB]\neq 1$. Suppose for a
contradiction that this is not the case, so that $[A,B]\in
Z(\mathrm{GL}(n,q))$, i.e., that $(B^{-1})^{A}B=kI_{n}$ for some
$k\in\mathbb{F}_{q}^{\times}$. Then $(B^{-1})^{A}=kB^{-1}$. As $B$ has
eigenvalue $1$ with algebraic multiplicity $n$, while $kB^{-1}$ has eigenvalue
$k$, we deduce that $1=k=[A,B]$. However, $(AB)_{11}=1$ and $(BA)_{11}=0$, a
contradiction. ∎

######  Lemma 5.5.

Let $A\in H$ such that $\langle A\rangle$ acts irreducibly on $V$ and
$A^{q-1}\in Z$. Then there exist $X\in\mathcal{U}$ and $B\in H_{X}$ such that
$ZA\sim ZB$.

###### Proof.

Note that $q\neq 2$. By Lemma 4.3, we may assume that $A$ is the (monomial)
companion matrix $C(x^{n}-b)$, for some $b\in\mathbb{F}_{q}^{\times}$ with
$x^{n}-b$ irreducible over $\mathbb{F}_{q}$. Let
$X:=\langle\begin{matrix}(1&0&0&\cdots&0)\end{matrix}\rangle\in\mathcal{U}$.
Using Lemma 2.2 and the fact that the monomial matrices in $H$ form a proper
subgroup, it suffices to find a monomial matrix $B\in H_{X}$ with $[A,B]\notin
Z$.

If $n=2$, then $b=-\det(A)=-1$, hence $x^{2}+1$ is irreducible over
$\mathbb{F}_{q}$, yielding $q\neq 5$. Thus we can set
$B=\mathrm{diag}(\omega,\omega^{-1})$ for some primitive element $\omega$ of
$\mathbb{F}_{q}$. If instead $n>2$, then we can set
$B=I_{n}-E_{n-1,n-1}-E_{n,n}+E_{n-1,n}-E_{n,n-1}$, as the $(1,1)$ entry of
$[A,B]$ is equal to $0$. ∎

######  Lemma 5.6.

Let $A\in H$ such that $\langle A\rangle$ acts irreducibly on $V$ and
$A^{q-1}\notin Z$.

  1. (i)

Suppose that $n>2$ or $q\not\equiv 3\pmod{4}$. Then there exist
$X\in\mathcal{U}$ and $K\in H_{X}$ such that $ZA\sim ZK$.

  2. (ii)

Suppose that $n=2$ and $q\equiv 3\pmod{4}$. Then there exists $D\in H$ such
that $\langle D\rangle$ acts irreducibly on $V$, with $D^{2},D^{q-1}\in Z$ and
$ZA\sim ZD$.

###### Proof.

By [15, Proposition 3.6.1], $A$ lies in a Singer subgroup $S$ of
$\mathrm{GL}(n,q)$ (a cyclic subgroup of order $q^{n}-1$). Thus
$Z(\mathrm{GL}(n,q))<S$ and $N:=N_{\mathrm{GL}(n,q)}(S)$ is the group $S\mkern
1.5mu{:}\mkern 1.5mu\langle B\rangle$ of order $n(q^{n}-1)$, where
$B\in\mathrm{GL}(n,q)$ is similar to the companion matrix $C(x^{n}-1)$ and
satisfies $F^{B}=F^{q}$ for each $F\in S$ (see [26, pp. 187–188] and [25, p.
497]). As $C(x^{n}-1)$ stabilises the subspace in $\mathcal{U}$ spanned by the
all-ones vector, $B$ also stabilises some $X\in\mathcal{U}$. Note that
$\det(B)=\det(C(x^{n}-1))$ is equal to $1$ if $q$ is even or $n$ is odd, and
$-1$ otherwise. Additionally, $[A,B]=A^{-1}A^{B}=A^{q-1}\notin Z$. It is also
easy to see that $|N|<|H|$, and hence $\langle A,B,Z\rangle\leqslant H\cap
N<H$.

We now prove (i). By Lemma 2.2, it suffices to show that there exists a matrix
$K\in H_{X}$, with $[A,K]\notin Z$ and $\langle A,K,Z\rangle<H$. If $n$ is odd
or $q$ is even, then set $K=B$. If instead $n=2$ and $q\equiv 1\pmod{4}$, then
we can set $K=\alpha B$ for some square root $\alpha\in\mathbb{F}_{q}$ of
$-1$. Finally, if $q$ is odd and $n$ is even and greater than $2$, then
$B^{2}\in H_{X}$. Additionally, $[A,B^{2}]=A^{q^{2}-1}$. As $\langle A\rangle$
acts irreducibly on $V$, Lemma 4.4 yields $A^{q^{2}-1}\notin Z$. Thus we can
set $K=B^{2}$.

Next, we prove (ii). Let $R$ be a generator for $S$ and $T:=R^{(q-1)/2}$. Then
$\det(R)$ is a primitive element of $\mathbb{F}_{q}$ [4, p. 453], and so
$\det(T)=-1$. Thus $\langle A,TB,Z\rangle\leqslant H\cap N<H$. As $A$ and $T$
lie in the cyclic group $S$, we deduce that $[A,TB]=[A,B]\notin Z$. Hence by
Lemma 2.2, $ZA\sim ZTB$.

Now, as $|B|=2$, we see that $(TB)^{2}=TT^{B}=T^{q+1}$. Since $|R|=q^{2}-1$,
it follows that $|(TB)^{2}|=2$. Hence $(TB)^{2}$ is the unique involution
$-I_{2}$ of $S$, and $(TB)^{q-1}\in Z$, since $2\mid(q-1)$. Suppose for a
contradiction that $TB$ stabilises a subspace $U\in\mathcal{U}$. Then there
exists $\lambda\in\mathbb{F}_{q}^{\times}$ such that $u^{TB}=\lambda u$ and
$u^{(TB)^{2}}=\lambda^{2}u$ for all $u\in U$. However, $u^{(TB)^{2}}=-u$, and
there is no $\lambda\in\mathbb{F}_{q}^{\times}$ with $\lambda^{2}=-1$.
Therefore, $\langle TB\rangle$ acts irreducibly on $V$, and we can set $D=TB$.
∎

###### Proof of Theorem 5.1.

Let $x,y\in G\setminus\\{1\\}$. We will show that $d(x,y)\leqslant 4$. By
Lemma 5.3, there is a path in $\Xi(G)$ of length at most two joining any two
elements of $G\setminus Z(G)$ that stabilise a one-dimensional subspace of
$V$. Furthermore, Lemmas 5.4–5.6 show that either there exists an element
$u\in H\setminus\\{1\\}$ such that $\langle u\rangle$ stabilises a one-
dimensional subspace of $V$ and $d(x,u)\leqslant 1$; or $n=2$, $q\equiv
3\pmod{4}$, $\langle x\rangle$ acts irreducibly on $V$, and $x^{q-1}\neq 1$.
By the symmetry in $x$ and $y$, it follows that if $n>2$ or $q\not\equiv
3\pmod{4}$, then $d(x,y)\leqslant 4$, as required.

Suppose therefore that $n=2$ and $q\equiv 3\pmod{4}$. By the previous
paragraph, we may assume that $\langle x\rangle$ acts irreducibly on $V$, and
that $x^{q-1}\neq 1$. Lemma 5.6 shows that there exists an element $D\in H$
whose image $g$ in $G$ is adjacent to $x$ in $\Xi(G)$, such that $D^{2}\in Z$.
Hence $|g|=2$, and $x,g\in K\setminus Z(K)$ for some maximal subgroup $K$ of
$G$. Thus if $G$ contains a maximal subgroup $M$ of even order with $y\in
M\setminus Z(M)$, then Lemma 2.6 yields $d(x,y)\leqslant 4$.

If instead there is no such $M$, then Proposition 2.3 implies that $y\in
L\setminus Z(L)$ for some maximal subgroup $L$ of odd order. By [29, Theorem
2], $L$ is the stabiliser of a one-dimensional subspace of $V$. Now, Lemma 5.6
shows that $\langle D\rangle$ acts irreducibly on $V$, and $D^{q-1}\in Z$.
Thus we deduce from Lemma 5.5 that $g\sim k$ for some $k\in G$ that stabilises
a one-dimensional subspace of $V$, and Lemma 5.3 yields $d(k,y)\leqslant 2$.
Thus $d(x,y)\leqslant d(x,g)+d(g,k)+d(k,y)\leqslant 4$. ∎

Using Magma, we see that $\mathrm{diam}(\Xi(G))=2$ when $n=2$ and
$q\in\\{4,5,7,8,9,16\\}$, or $n\in\\{3,4\\}$ and $q=2$; while
$\mathrm{diam}(\Xi(G))=3$ when $n=2$ and $q\in\\{11,13\\}$, or $n=3$ and
$q\in\\{3,4\\}$.

###  5.2. Unitary groups

Assume that $H=\mathrm{SU}(n,q)$, with $n\geqslant 3$, and $q\geqslant 3$ if
$n=3$, so that $G$ is simple. In fact, by Proposition 1.5 and Theorem 2.7, we
may assume that $n$ is prime.

######  Theorem 5.7.

Let $G$ be the unitary group $\mathrm{PSU}(n,q)$, with $n$ an odd prime.

  1. (i)

$\Xi(G)$ is connected with diameter at most $5$.

  2. (ii)

Suppose that $n=7$ and $q=2$. Then $\Xi(G)$ is connected with diameter $4$.

Let $V$ be the natural module $\mathbb{F}_{\\!q^{2}}^{n}$ for
$H=\mathrm{SU}(n,q)$, equipped with the unitary form with Gram matrix $I_{n}$,
and fix a corresponding basis $\\{e_{1},\ldots,e_{n}\\}$ for $V$.

######  Lemma 5.8.

Suppose that $n=3$, let $\omega$ be a primitive element of
$\mathbb{F}_{\\!q^{2}}$, and let $\lambda:=\omega^{q-1}$. For each
$i\in\\{1,2,3\\}$, let $B_{i}:=\lambda I_{3}+(\lambda^{-2}-\lambda)E_{ii}$,
and let $A_{1}$ and $A_{2}$ be $H$-conjugates of $B_{1}$.

  1. (i)

$B_{i}\in H\setminus Z$ for each $i$.

  2. (ii)

$B_{2}$ and $B_{3}$ are each conjugate to $B_{1}$ in $H$.

  3. (iii)

$\langle A_{1},A_{2}\rangle$ is a proper subgroup of $H$ that stabilises a
one-dimensional subspace of $V$.

  4. (iv)

If $A_{1}$ is not adjacent in $\Xi(H)$ to any $B_{i}$, then $A_{1}$ is
diagonal.

###### Proof.

Since $\lambda^{q}=\lambda^{-1}$, and $\det(B_{i})=1$ and $B_{i}\notin Z$ for
each $i$, we obtain (i). For (ii), note that $E_{1,2}+E_{2,1}-E_{3,1}$ and
$E_{1,3}-E_{2,2}+E_{3,1}$ lie in $H$ and conjugate $B_{1}$ to $B_{2}$ and
$B_{3}$, respectively.

To prove (iii), we may assume that $A_{1}=B_{1}$. Let $F\in H$ such that
$A_{2}=B_{1}^{F}$, and note that $B_{1}$ and $A_{2}$ act as $\lambda$ on the
subspaces $E:=\langle e_{2},e_{3}\rangle$ and $E^{F}$ of $V$, respectively.
Hence $\langle B_{1},A_{2}\rangle$ stabilises each subspace of $E\cap E^{F}$,
which has positive dimension since $\dim(V)=3$. The group $H$ acts irreducibly
on $V$, and thus properly contains $\langle B_{1},A_{2}\rangle$. This
completes the proof of (iii).

By (ii) and (iii), if an $H$-conjugate of $B_{1}$ is not adjacent in $\Xi(H)$
to any $B_{i}$, then that conjugate lies in $C_{H}(\\{B_{1},B_{2},B_{3}\\})$,
which consists of diagonal matrices. Thus (iv) follows. ∎

######  Lemma 5.9.

Suppose that $n$ is an odd prime.

  1. (i)

The companion matrix $C(x^{n}-1)$ is an element of $H$.

  2. (ii)

Let $R$ be an element of $H$ that is conjugate to $C(x^{n}-1)$. Then $ZR$ is
adjacent in $\Xi(G)$ to an involution of $G$.

  3. (iii)

Let $R$ and $S$ be $H$-conjugates of the companion matrix $C(x^{n}-1)$. Then
$d(ZR,ZS)$ is at most $3$ if $n=3$, or at most $2$ otherwise.

###### Proof.

(i) This holds since $C(x^{n}-1)^{-1}=C(x^{n}-1)^{T}$ and
$\det(C(x^{n}-1))=1$.

(ii) By (i), we may assume without loss of generality that $R=C(x^{n}-1)$. If
$q$ is odd, then let $A:=I_{n}-2E_{n-1,n-1}-2E_{n,n}\in H$, so that the
$(1,1)$ and $(n,n)$ entries of $[R,A]$ are equal to $-1$ and $1$,
respectively. If instead $q$ is even, then let
$A:=I_{n}+\sum_{i,j=n-1}^{n}E_{i,j}\in H$, so that the $(1,1)$ entry of
$[R,A]$ is equal to $0$. In either case, $[R,A]\notin Z$. Moreover, $R$ and
$A$ are monomial, and so $\langle R,A,Z\rangle<H$. Thus Lemma 2.2 shows that
$ZR\sim ZA$. As $A$ is an involution, so is $ZA$.

(iii) We may assume that $R=C(x^{n}-1)$ and $d(ZR,ZS)>1$. Then $R$ stabilises
the subspace $X$ of $V$ spanned by the all-ones vector. Let $F\in H$ such that
$S=R^{F}$, and let $L:=H_{X}$, so that $R\in L$ and $S\in L^{F}$.
Additionally, let $L_{0}:=H_{\langle e_{1}\rangle}$. It is easy to show that
$C_{L_{0}}(R)=Z$, and thus $C_{L_{0}^{F}}(S)=Z$. It also follows from Lemma
4.5(i) that if $A\in L\cup L_{0}$ satisfies $[R,A]\in Z$, then $[R,A]=1$. As
$Z\leqslant L$, we deduce from Lemma 2.2 that if $[R,B]\neq 1$ for some $B\in
L$, then $ZR\sim ZB$. Similarly, if $[S,D]\neq 1$ for some $D\in L^{F}$, then
$ZS\sim ZD$. We split the remainder of the proof into three cases.

Case (a): $n\geqslant 7$, or $n=5$ and $q\neq 4$. By Theorem 4.6, the
pointwise stabiliser $L\cap L^{F}\cap L_{0}\cap L_{0}^{F}$ in $H$ of
$\\{X,X^{F},\langle e_{1}\rangle,\langle e_{1}\rangle^{F}\\}$ contains a non-
scalar matrix $D$. The previous paragraph shows that $D$ centralises neither
$R$ nor $S$, and in fact that $ZR\sim ZD\sim ZS$.

Case (b): $n=5$ and $q=4$. Let $v\in X$ be the all-ones vector. The unitary
form on $V$ maps $(v,v)$ to $1\in\mathbb{F}_{q}$, and so $X$ is non-
degenerate. Straightforward computations in Magma show that $|L\cap L^{F}|$ is
even (for any $F\in H$), while $|C_{H}(R)|=625$ (and hence $|C_{H}(S)|=625$).
It follows from the second last paragraph that $ZR\sim ZD\sim ZS$ for each
involution $D\in L\cap L^{F}$.

Case (c): $n=3$. For each $i\in\\{1,2,3\\}$, let $B_{i}\in H\setminus Z$ be as
in Lemma 5.8. Then $B_{i}\in L_{0}\setminus Z$, and so $[R,B_{i}]\notin Z$.
Additionally, since $Z$, $R$ and $B_{i}$ are monomial matrices, $\langle
Z,R,B_{i}\rangle<H$. Thus Lemma 2.2 gives $ZR\sim ZB_{i}$. Similarly, $ZS\sim
ZB_{i}^{F}$. Recall also from Lemma 5.8(ii)–(iii) that $\langle
B_{i},B_{1}^{F}\rangle$ stabilises a one-dimensional subspace of $V$. Hence,
as in the third last paragraph, if $\\{B_{1}^{F},B_{i}\\}$ is an edge of
$\Xi(H)$ for some $i$, then $ZB_{i}\sim ZB_{1}^{F}$, and so ${ZR\sim
ZB_{i}\sim ZB_{1}^{F}\sim ZS}$. Otherwise, $B_{1}^{F}$ is diagonal by Lemma
5.8(iv), and so replacing $B_{i}$ with $B_{1}^{F}$ in the above argument
yields $ZR\sim ZB_{1}^{F}$. Therefore, $ZR\sim ZB_{1}^{F}\sim ZS$. ∎

###### Proof of Theorem 5.7.

(i) Let $x,y\in G\setminus Z(G)$. We will show that $d(x,y)\leqslant 5$. By
Proposition 2.3, each of $x$ and $y$ is non-central in some maximal subgroup.
Using Lemma 2.6, we may assume that each maximal subgroup $K$ of $G$ with
$x\in K\setminus Z(K)$ has odd order. By [29, Theorem 2], $K=N_{H}(S)/Z$,
where $S$ is a Singer subgroup of $H$, i.e., the intersection of $H$ and a
Singer subgroup of $\mathrm{GL}(n,q^{2})$. It follows from [25, p. 497 & p.
512] that $N_{H}(S)=S\mkern 1.5mu{:}\mkern 1.5mu\langle C\rangle$ for some
$H$-conjugate $C$ of $C(x^{n}-1)$.

Now, by Lemma 5.9(ii), $ZC\sim r$ for some involution $r\in G$, and so
$ZC,r\in L\setminus Z(L)$ for some maximal subgroup $L$ of $G$ of even order.
As $|C|=n$ is prime, each non-identity element of $\langle ZC\rangle$ lies in
$L\setminus Z(L)$. Since $Z\leqslant S$, it follows that $x=ZAC^{i}$ for some
$A\in S\setminus Z$ and some $i\in\\{0,1,\ldots,n-1\\}$. By [34, Proposition
4.2.2], $\langle A\rangle$ acts irreducibly on $\mathbb{F}_{\\!q^{2}}^{n}$.
Additionally, as in the proof of Lemma 5.6 (but now working over
$\mathbb{F}_{\\!q^{2}}$), we see that $[A,C]=A^{q^{2}-1}$. By Lemma 4.4,
$A^{q^{4}-1}\notin Z$, and so $[A,C]\notin Z$. Moreover, $\langle
A,C,Z\rangle\leqslant N_{H}(S)<H$. Therefore, Lemma 2.2 yields $ZA\sim ZC$. It
is now easy to see that $ZAC^{i}\sim ZC$ for all $i$, and in particular,
$x\sim ZC$.

If $y\in M\setminus Z(M)$ for some maximal subgroup $M$ of $G$ of even order,
then since $ZC\sim r$ and $|r|=2$, Lemma 2.6 shows that $d(ZC,y)\leqslant 4$.
Hence $d(x,y)\leqslant 5$. Otherwise, $y$ lies in a $G$-conjugate of
$N_{H}(S)/Z$. By the previous paragraph, $y\sim ZD$ for some $H$-conjugate $D$
of $C$. Since $x\sim ZC$, and since $d(ZC,ZD)\leqslant 3$ by Lemma 5.9(iii),
we obtain $d(x,y)\leqslant 5$.

(ii) By [17, Remark 1.3] (see also [18, Ch. 4]), the intersection graph of $G$
has diameter $5$. Thus $\mathrm{diam}(\Xi(G))\geqslant 4$ by Lemma 2.4. It
remains to show that $d(x,y)\leqslant 4$ for all $x,y\in G\setminus\\{1\\}$.
In what follows, all information about $G$ is determined via Magma, except
where stated otherwise.

If $|x|,|y|\neq 43$, then each of $x$ and $y$ is adjacent in $\Xi(G)$ to an
involution, and Lemma 2.6 yields $d(x,y)\leqslant 4$. Assume from now on that
$|x|=43$. Then $x$ lies in no maximal subgroup of $G$ of even order. As in the
proof of (i), $x\sim t$, where $t$ is the image in $G$ of some $G$-conjugate
of $C(x^{7}-1)$. Since $n>3$, it follows from Lemma 5.9(iii) that if $|y|=43$,
then $d(x,y)\leqslant 4$.

Suppose finally that $|y|\neq 43$, and let $T:=\langle t\rangle$. Then there
exist maximal subgroups $K$ and $L$ of $G$ such that $y\in K\setminus Z(K)$,
$t\in L\setminus Z(L)$, and either:

  1. (I)

$|K\cap L|>|C_{G}(t)|+|Z(K)|$; or

  2. (II)

$Z(K)=1$, $C_{L}(t)=T$, $T\cap K=1$, and $|K|\,|L|>|G|$.

In case (I), there exists an element $f\in K\cap L$ that centralises neither
$t$ nor $K$. Hence ${t\sim f}$, and $d(f,y)\leqslant 2$ by Lemma 2.1, yielding
$d(t,y)\leqslant 3$. In case (II), we observe that $K\cap L>1$, and that
$t\sim w$ for each non-identity $w\in K\cap L$. As $d(w,y)\leqslant 2$ by
Lemma 2.1, we again obtain $d(t,y)\leqslant 3$. We conclude in general that
$d(x,y)\leqslant d(x,t)+d(t,y)\leqslant 4$. ∎

Using Magma, we observe that the non-commuting, non-generating graphs of
$\mathrm{PSU}(3,3)$, $\mathrm{PSU}(3,4)$ and $\mathrm{PSU}(4,2)$ have
diameters $2$, $2$ and $3$, respectively.

###  5.3. The non-generating graph of a non-abelian finite simple group

###### Proof of Theorem 1.8.

Let $x,y\in G\setminus\\{1\\}$, and let $M_{1}$ and $M_{2}$ be maximal
subgroups of $G$ containing $x$ and $y$, respectively. If $|M_{1}|$ and
$|M_{2}|$ are even, then $\langle a,b\rangle$ is dihedral for involutions
$a\in M_{1}$ and $b\in M_{2}$. Hence $(x,a,b,y)$ contains a path from $x$ to
$y$ in $\overline{\Gamma}(G)$, and $d(x,y)\leqslant 3$. Thus we are done if
every maximal subgroup of $G$ has even order.

Assume now that $|M_{1}|$ is odd. By Theorems 2.7 and 1.1, if $G$ is not
unitary of odd prime dimension, then $\mathrm{diam}(\Xi(G))\leqslant 4$. As
$\Xi(G)$ is a spanning subgraph of $\overline{\Gamma}(G)$, it follows in this
case that $\mathrm{diam}(\overline{\Gamma}(G))\leqslant 4$.

Suppose therefore that $G=\mathrm{PSU}(n,q)$, with $n$ an odd prime. As in the
proof of Theorem 5.7, $M_{1}$ is the image in $G$ of the subgroup $S\mkern
1.5mu{:}\mkern 1.5mu\langle C\rangle$ of $\mathrm{SU}(n,q)$, with $S$ a Singer
subgroup of $\mathrm{SU}(n,q)$ and $C$ a conjugate of the companion matrix
$C(x^{n}-1)$. By Lemma 5.9(ii), there exists an involution $a\in G$ such that
the image $c$ of $C$ in $G$ is adjacent to $a$ in $\Xi(G)$, and hence in
$\overline{\Gamma}(G)$.

Now, if $M_{2}$ contains an involution $b$, then $(x,c,a,b,y)$ contains a path
from $x$ to $y$ in $\overline{\Gamma}(G)$, and $d(x,y)\leqslant 4$. Otherwise,
by the previous paragraph, $y\sim c^{\prime}$ for some $G$-conjugate
$c^{\prime}$ of $c$. Moreover, $c$ and $c^{\prime}$ stabilise one-dimensional
subspaces $X$ and $X^{\prime}$, respectively, of $\mathbb{F}_{\\!q^{2}}^{n}$.
Since $q\neq 2$ when $n=3$, we deduce from Theorem 4.6 that $G_{X}\cap
G_{X^{\prime}}$ contains an element $t\neq 1$. Hence $(x,c,t,c^{\prime},y)$
contains a path from $x$ to $y$ in $\overline{\Gamma}(G)$, and
$d(x,y)\leqslant 4$. Therefore, $\mathrm{diam}(\overline{\Gamma}(G))\leqslant
4$.

Finally, suppose that $G$ is the baby monster group or $\mathrm{PSU}(7,2)$.
Then the intersection graph of $G$ is connected with diameter $5$ [17, Theorem
1.1 & Remark 1.3], and so Lemma 2.4 yields
$\mathrm{diam}(\overline{\Gamma}(G))\geqslant 4$. By the previous paragraphs,
we conclude that $\mathrm{diam}(\overline{\Gamma}(G))=4$. ∎

### Acknowledgments

This work was supported by the University of St Andrews (St Leonard’s
International Doctoral Fees Scholarship & School of Mathematics and Statistics
PhD Funding Scholarship), and by EPSRC grant number EP/W522422/1. The author
is grateful to Colva Roney-Dougal and Peter Cameron for helpful discussions
regarding the original thesis on which this work is based, and to Colva for
additional feedback on this paper.

## References

  * [1] W. Bosma, J. Cannon, and C. Playoust.  The Magma algebra system. I. The user language.  J. Symbolic Comput., 24(3-4):235–265, 1997.
  * [2] J. N. Bray, D. F. Holt, and C. M. Roney-Dougal.  The maximal subgroups of the low-dimensional finite classical groups.  CUP, Cambridge, 2013.
  * [3] T. Breuer, R. M. Guralnick, and W. M. Kantor.  Probabilistic generation of finite simple groups. II.  J. Algebra, 320(2):443–494, 2008.
  * [4] J. R. Britnell, A. Evseev, R. M. Guralnick, P. E. Holmes, and A. Maróti.  Sets of elements that pairwise generate a linear group.  J. Combin. Theory Ser. A, 115(3):442–465, 2008.
  * [5] T. Burness, R. Guralnick, and S. Harper.  The spread of a finite group.  Ann. of Math. (2), 193(2):619–687, 2021.
  * [6] T. C. Burness and M. Giudici.  Classical groups, derangements and primes.  CUP, Cambridge, 2016.
  * [7] T. C. Burness, R. M. Guralnick, and J. Saxl.  On base sizes for algebraic groups.  J. Eur. Math. Soc. (JEMS), 19(8):2269–2341, 2017.
  * [8] T. C. Burness, A. Lucchini, and D. Nemmi.  On the soluble graph of a finite group.  J. Combin. Theory Ser. A, 194:105708, 2023.
  * [9] P. J. Cameron.  Graphs defined on groups.  Int. J. Group Theory, 11(2):53–107, 2022.
  * [10] P. J. Cameron, S. D. Freedman, and C. M. Roney-Dougal.  The non-commuting, non-generating graph of a nilpotent group.  Electron. J. Combin., 28(1):Paper No. 1.16, 15, 2021.
  * [11] L. Carlitz.  Note on a quartic congruence.  Amer. Math. Monthly, 63:569–571, 1956.
  * [12] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson.  Atlas of finite groups.  Oxford University Press, Eynsham, 1985.
  * [13] E. Crestani and A. Lucchini.  The non-isolated vertices in the generating graph of a direct powers of simple groups.  J. Algebraic Combin., 37(2):249–263, 2013.
  * [14] B. Csákány and G. Pollák.  The graph of subgroups of a finite group.  Czechoslovak Math. J., 19(94):241–247, 1969.
  * [15] W. de Launey and D. Flannery.  Algebraic design theory.  Amer. Math. Soc., Providence, RI, 2011.
  * [16] S. D. Freedman.  The non-commuting, non-generating graph of a non-simple group (submitted).  arXiv:2211.08869.
  * [17] S. D. Freedman.  The intersection graph of a finite simple group has diameter at most 5\.  Arch. Math. (Basel), 117(1):1–7, 2021.
  * [18] S. D. Freedman.  Diameters of graphs related to groups and base sizes of primitive groups.  PhD thesis, University of St Andrews, May 2022.
  * [19] The GAP Group.  GAP – Groups, Algorithms, and Programming, Version 4.8.4, 2016\.
  * [20] G. Glauberman.  Central elements in core-free groups.  J. Algebra, 4:403–420, 1966.
  * [21] D. Gorenstein, R. Lyons, and R. Solomon.  The classification of the finite simple groups. Number 3. Part I. Chapter A.  Amer. Math. Soc., Providence, RI, 1998.
  * [22] R. L. Griess, Jr.  Finite groups whose involutions lie in the center.  Quart. J. Math. Oxford Ser. (2), 29(115):241–247, 1978.
  * [23] G. Heide, J. Saxl, P. H. Tiep, and A. E. Zalesski.  Conjugacy action, induced representations and the Steinberg square for simple groups of Lie type.  Proc. Lond. Math. Soc. (3), 106(4):908–930, 2013.
  * [24] I. N. Herstein.  A remark on finite groups.  Proc. Amer. Math. Soc., 9:255–257, 1958.
  * [25] M. D. Hestenes.  Singer groups.  Canadian J. Math., 22:492–513, 1970.
  * [26] B. Huppert.  Endliche Gruppen. I.  Springer-Verlag, Berlin-New York, 1967.
  * [27] F. Knüppel and G. Thomsen.  Involutions and commutators in orthogonal groups.  J. Austral. Math. Soc. Ser. A, 65(1):1–36, 1998.
  * [28] R. Lidl and H. Niederreiter.  Finite fields.  CUP, Cambridge, second edition, 1997.
  * [29] M. W. Liebeck and J. Saxl.  On point stabilizers in primitive permutation groups.  Comm. Algebra, 19(10):2777–2786, 1991.
  * [30] M. W. Liebeck, J. Saxl, and G. M. Seitz.  Subgroups of maximal rank in finite exceptional groups of Lie type.  Proc. London Math. Soc. (3), 65(2):297–325, 1992.
  * [31] A. Lucchini and D. Nemmi.  On the connectivity of the non-generating graph.  Arch. Math. (Basel), 118(6):563–576, 2022.
  * [32] S. Perlis.  Theory of matrices.  Dover Publications, Inc., New York, 1991.
  * [33] J. S. Rose.  On finite insoluble groups with nilpotent maximal subgroups.  J. Algebra, 48(1):182–196, 1977.
  * [34] M. W. Short.  The primitive soluble permutation groups of degree less than $256$.  Springer-Verlag, Berlin, 1992.
  * [35] M. Suzuki.  On a class of doubly transitive groups.  Ann. of Math. (2), 75:105–145, 1962.
  * [36] R. A. Wilson.  The finite simple groups.  Springer-Verlag London, Ltd., London, 2009.
  * [37] R. A. Wilson.  Maximal subgroups of sporadic groups.  In Finite simple groups: thirty years of the atlas and beyond, pages 57–72. Amer. Math. Soc., Providence, RI, 2017.


#  A Multi-modal and Multi-task Learning Method for Action Unit and Expression
Recognition

Yue Jin111These authors contributed equally to this work.
China Pacific Insurance (Group) Co., Ltd.
719 Yishan Road, Shanghai, China
<EMAIL_ADDRESS>Tianqing Zheng111These authors contributed equally to
this work.
Shanghai Jiaotong University
800 Dongchuan Road, Shanghai, China
<EMAIL_ADDRESS>Chao Gao
China Pacific Insurance (Group) Co., Ltd.
719 Yishan Road, Shanghai, China
<EMAIL_ADDRESS>Guoqiang Xu
China Pacific Insurance (Group) Co., Ltd.
719 Yishan Road, Shanghai, China
<EMAIL_ADDRESS>
###### Abstract

Analyzing human affect is vital for human-computer interaction systems. Most
methods are developed in restricted scenarios which are not practical for in-
the-wild settings. The Affective Behavior Analysis in-the-wild (ABAW) 2021
Contest provides a benchmark for this in-the-wild problem. In this paper, we
introduce a multi-modal and multi-task learning method by using both visual
and audio information. We use both AU and expression annotations to train the
model and apply a sequence model to further extract associations between video
frames.

We achieve an AU score of 0.712 and an expression score of 0.477 on the
validation set. These results demonstrate the effectiveness of our approach in
improving model performance.

##  1 Introduction

Nowadays, analyzing human affect is becoming more and more important for
Artificial Intelligence (AI) systems, especially for human-computer
interaction. The ability for machines to recognize the human face is mature,
but the ability to understand human emotions still has a long way to go.

The Affective Behavior Analysis in-the-wild (ABAW2) 2021 Competition
[6][10][12] [8][7][13] [9][21] is held by Kollias et al. in conjunction with
ICCV 2021. It provides a benchmark for three main tasks of Valence- Arousal
Estimation, seven Basic Expression Classification and twelve Action Unit
Detection[3]. The Facial Action Coding System (FACS) is a comprehensive system
for describing facial movement. Action Units (AU) are individual components of
muscle movements[3].

All three tasks are based on a large-scale in-the-wild database, Aff-
Wild2[12][11]. It consists of 548 videos with 2,813,201 frames and provides
annotations for all of these tasks. All videos are collected from Youtube
which provides a real-world setting. So it is much more difficult to analyze
affect than for other datasets. Data imbalance issues make this competition
quite challenging. See figure.1.

To tackle these problems, we propose a multi-task method to learn Action Unit
(AU) and facial expressions jointly using both visual and audio information.
First, we train a visual model. Second, we freeze the parameters of the visual
model and train the audio model. Third, we concatenate both visual and audio
features and train the sequence model.

Figure 1: Statistics on the number of AUs and expressions labeled in each
category. Figure 2: A multi-modal framework.

##  2 Related Work

In the first ABAW2 competition, lots of teams presented great methods for this
challenging problem.

Deng et al.[2] proposed a multi-task learning method to learn from missing
labels. They used a data balancing technique to the dataset. First, they used
the ground truth labels of all three tasks to train a teacher model. Secondly,
they used the output of the teacher model as the soft labels. They used the
soft labels and the ground truth labels to train their student models.

Kuhnke and Rumberg[14] proposed a two-stream aural-visual model. Audio and
image streams are first proposed separately and fed into a CNN network. Then
they use temporal convolutions to the image stream. They use additional
features extracted during facial alignment and correlations between different
emotion representations to boost their performance.

##  3 Method

We use a multi-modal multi-task learning method for facial action units and
expression recognition. See Figure.2

First, we train the visual model separately by using both AU and expression
annotations. Secondly, we freeze the parameters of the visual stream and add
an audio stream to extract the audio feature. Finally, the visual feature and
the audio feature are concatenated and fed into a transformer encoder to
further extract temporal features.

Figure 3: A multi-task visual stream training framework.

###  3.1 Multi-Task Visual model

A multi-task framework is used to train the visual model, see Figure.3.

First, we train the visual backbone with Cosface loss.[20] The dataset we use
is Glint360K.[1] It is the largest and cleanest face recognition dataset,
which contains 17,091,657 images of 360,232 individuals. Using the pretrained
visual backbone boosts the performance because it provides sufficient human
face information.

Both AU and expression heads share weights of the same backbone. AU and
expression heads are fully connected layers that map features to the number of
output classes. The annotations of AU and expression is incomplete, that is,
some frames have both AU and expression annotation, but other frames only have
one of these two annotations. To tackle this problem, we design two ways to do
backpropagation when training.

1) Epoch by epoch: The parameters of the AU head and expression head are
updated in rotation epoch by epoch. For example, we have a set of images,
annotations of AU, and annotations of expression. At epoch 1, we use images
with expression annotations, do backpropagation, and only update the
parameters of backbone and expression head. At epoch 2, we use images with AU
annotations, do backpropagation, and only update the parameters of the
backbone and AU head. Then we repeat the above steps.

2) Batch by batch: The parameters of the AU head and expression head are
updated in rotation batch by batch. For example, for the first batch, we use
images with expression annotations, do backpropagation, and only update the
parameters of the backbone and expression head. For the next batch, we use
images with AU annotations, do backpropagation, and only update the parameters
of the backbone and AU head. Then we repeat the above steps.

### Loss Function

For action unit recognition, we use BCE loss with position weight to tackle
the imbalance of positive samples and negative samples. It’s possible to
trade-off recall and precision by adding weights to positive examples.

$L_{BCE}=\mathbb{E}[-\sum(w_{i}t_{i}\cdot logp_{i}+(1-t_{i})\cdot
log(1-p_{i}))]$ (1)

For expression recognition, we use focal loss[15] to tackle class imbalance
problem. It uses a modulating factor to the cross-entropy loss to reduce the
loss contribution from easy examples and elevate the importance of hard
examples.

$FL(p_{t})=-\alpha_{t}(1-p_{t})^{\gamma}log(p_{t})$ (2)

###  3.2 Multi-Modal Sequence Model

The Multi-modal Sequence model is composed of two sub-modal modules(Visual
Model and Audio Model), a fusion layer, and an encoder layer from
transformer[19].

The input of the network is a video and the output is the predicted labels of
every frame in the video.

First, image frames and the audio stream are extracted from the video and fed
into the visual and audio models respectively.

Visual model: The Visual Model is pretrained using the multi-task method in
Section 3.1 to extract visual features of a single frame.

Audio model: For audio, a Mel spectrogram is computed using the TorchAudio
package and TDNN[17] is used as the backbone to extract the audio features.

Sequence model: Then, the audio features and the visual features are aligned
and fused to get the multi-model features. The multi-model features are fed
into the encoder network from transformer[19] to extract the sequence
features;

Finally, a fully connected layer is used to get the prediction result of each
frame.

##  4 Experiments

###  4.1 Dataset

Aff-wild2 dataset[12][11] is used for both AU and expression recognition. We
discard annotations with -1.

For AU recognition, we use BP4D[22] as an additional training dataset. This
replenishes the number of scarce categories, like AU15, AU23, AU24.

Because some of the images in the AU and expression validation sets appear in
each other’s training sets, we remove this part of the images that appear in
the expression training set when validating the AU metric to ensure that there
is no additional prior knowledge when validating the AU metric. The
corresponding operation is also performed when verifying the expression
metrics. Thus, we ensure that the validation set videos in AU and expression
recognition tasks are consistent and the validation set videos of each task do
not appear in the training set of the other task.

We use the cropped and aligned images provided in the Aff-wild2 dataset.

###  4.2 Experiment Settings

Our framework is implemented by using Pytorch[16].

Visual model setting: The face recognition model - IResNet100[4] provided by
Insightface***https://github.com/deepinsight/insightface is used as the
pretrained model. Other visual backbones, such as SENet[5] et.al. are also
trained with Cosface loss[20] using Glint360K[1] dataset.

We use the cropped and aligned images provided by Aff-wild2 dataset. The width
and height are set to 112 pixels. Data augmentations are random horizontal
flip, small random crop, and small random changes to hue, saturation, and
lightness. The mini-batch size is set to 64. We use SGD[18] optimizer with
momentum and the learning rate is set to 0.001.

Audio model setting: We use the following settings to compute a Mel
spectrogram of the audio:

  * •

number of mel filter banks $n_{mels}=64$

  * •

window size $w_{win}=10ms$

  * •

window stride $t_{stride}=5ms$

The output dimension of Time Delay Neural Network (TDNN[17])is set to 512.

Sequence model setting: The input number of frames is set to 30 and the number
of encoder layers from the transformer is set to 1. We use SGD[18] optimizer
with momentum and the learning rate is set to 0.01.

###  4.3 Evaluation Metric

For 12 Action Unit Detection, the performance metric is:

$0.5*F1\underline{~{}~{}}Score+0.5*Accuracy$ (3)

For 7 Basic Expression Classification, the performance metric is:

$0.67*F1\underline{~{}~{}}Score+0.33*Accuracy$ (4)

where F1 Score is the unweighted mean and Accuracy is the total accuracy.

Table 1: AU recognition results on validation dataset Method | Average F1 | Total Accuracy | Metric
---|---|---|---
Baseline[6] | 0.40 | 0.22 | 0.31
Ours | 0.545 | 0.879 | 0.712
Table 2: Expression recognition results on validation dataset Method | Average F1 | Total Accuracy | Metric
---|---|---|---
Baseline[6] | 0.30 | 0.50 | 0.366
Ours | 0.402 | 0.630 | 0.477

###  4.4 Results

We use the cropped and aligned images provided in the Aff-wild2 dataset when
doing validation. Some video frames are labeled, but there are no
corresponding images in the cropped and aligned folder. We discard these
frames with their labels when we evaluate our results on the validation set.

We achieve an AU score of 0.712 and an expression score of 0.554 on the
validation set. See Table.1 and Table.2. The results show that our method
greatly exceeds the baseline method.

##  5 Conclusion and Future Work

We proposed a multi-modal and multi-task learning method by using both visual
and audio information for the competition of ABAW2021 in ICCV2021. Our method
obtained a score of 0.712 on AU recognition and 0.554 on expression
recognition using the validation dataset. By using multi-modal information and
multi-task training method, the result of our approach far exceeding the
baseline result.

For future work, we will analyze our approach and do more detailed ablation
studies to verify the principle that the method works.

## References

  * [1] Xiang An, Xuhan Zhu, Yang Xiao, Lan Wu, Ming Zhang, Yuan Gao, Bin Qin, Debing Zhang, and Ying Fu.  Partial fc: Training 10 million identities on a single machine.  arXiv preprint arXiv:2010.05222, 2020.
  * [2] Didan Deng, Zhaokang Chen, and Bertram E Shi.  Multitask emotion recognition with incomplete labels.  In 2020 15th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2020), pages 592–599. IEEE, 2020.
  * [3] Paul Ekman and Erika L Rosenberg.  What the face reveals: Basic and applied studies of spontaneous expression using the Facial Action Coding System (FACS).  Oxford University Press, USA, 1997.
  * [4] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [5] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141, 2018.
  * [6] Dimitrios Kollias, Irene Kotsia, Elnar Hajiyev, and Stefanos Zafeiriou.  Analysing affective behavior in the second abaw2 competition, 2021.
  * [7] D Kollias, A Schulc, E Hajiyev, and S Zafeiriou.  Analysing affective behavior in the first abaw 2020 competition.  In 2020 15th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2020)(FG), pages 794–800, 2020.
  * [8] Dimitrios Kollias, Viktoriia Sharmanska, and Stefanos Zafeiriou.  Face behavior a la carte: Expressions, affect and action units in a single network.  arXiv preprint arXiv:1910.11111, 2019.
  * [9] Dimitrios Kollias, Viktoriia Sharmanska, and Stefanos Zafeiriou.  Distribution matching for heterogeneous multi-task learning: a large-scale face study.  arXiv preprint arXiv:2105.03790, 2021.
  * [10] Dimitrios Kollias, Panagiotis Tzirakis, Mihalis A Nicolaou, Athanasios Papaioannou, Guoying Zhao, Björn Schuller, Irene Kotsia, and Stefanos Zafeiriou.  Deep affect prediction in-the-wild: Aff-wild database and challenge, deep architectures, and beyond.  International Journal of Computer Vision, pages 1–23, 2019.
  * [11] Dimitrios Kollias and Stefanos Zafeiriou.  Aff-wild2: Extending the aff-wild database for affect recognition.  arXiv preprint arXiv:1811.07770, 2018.
  * [12] Dimitrios Kollias and Stefanos Zafeiriou.  Expression, affect, action unit recognition: Aff-wild2, multi-task learning and arcface.  arXiv preprint arXiv:1910.04855, 2019.
  * [13] Dimitrios Kollias and Stefanos Zafeiriou.  Affect analysis in-the-wild: Valence-arousal, expressions, action units and a unified framework.  arXiv preprint arXiv:2103.15792, 2021.
  * [14] Felix Kuhnke, Lars Rumberg, and Jörn Ostermann.  Two-stream aural-visual affect analysis in the wild.  In 2020 15th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2020), pages 600–605. IEEE, 2020.
  * [15] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [16] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * [17] Vijayaditya Peddinti, Daniel Povey, and Sanjeev Khudanpur.  A time delay neural network architecture for efficient modeling of long temporal contexts.  In Sixteenth annual conference of the international speech communication association, 2015.
  * [18] Sebastian Ruder.  An overview of gradient descent optimization algorithms.  arXiv preprint arXiv:1609.04747, 2016.
  * [19] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [20] Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou, Zhifeng Li, and Wei Liu.  Cosface: Large margin cosine loss for deep face recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5265–5274, 2018.
  * [21] Stefanos Zafeiriou, Dimitrios Kollias, Mihalis A Nicolaou, Athanasios Papaioannou, Guoying Zhao, and Irene Kotsia.  Aff-wild: Valence and arousal ‘in-the-wild’challenge.  In Computer Vision and Pattern Recognition Workshops (CVPRW), 2017 IEEE Conference on, pages 1980–1987. IEEE, 2017.
  * [22] Xing Zhang, Lijun Yin, Jeffrey F Cohn, Shaun Canavan, Michael Reale, Andy Horowitz, Peng Liu, and Jeffrey M Girard.  Bp4d-spontaneous: a high-resolution spontaneous 3d dynamic facial expression database.  Image and Vision Computing, 32(10):692–706, 2014.