Proof. Suppose $H_1, H_2 < G$ are subgroups at distance $d$ and let $A$ , $B$ be cyclic subgroups of $G$ of prime order with $A\leq H_1$ and $B\leq H_2$ . Every subgroup of $G$ nontrivially intersecting $A$ also nontrivially intersects $H_1$ and every subgroup of $G$ nontrivially intersecting $B$ also nontrivially intersects $H_2$ . Hence, if $A_0$ , $A_1, \ldots ,A_k$ is a path with $A_0=A$ and $A_k=B,$ then $H_1, A_1,\ldots , A_{k-1},H_2$ is also a path. Therefore, the distance between $H_1$ and $H_2$ provides a lower bound for the distance between $A$ and $B$ which, as the diameter is $d,$ is also equal to $d$ .

Proof. If $\mathrm {diam}(\Delta _G)=2,$ then for any two distinct cyclic subgroups of prime order, $A=\langle g_a\rangle $ and $B=\langle g_b\rangle ,$ there is a proper subgroup that contains both of them. The smallest such subgroup is $\langle g_a,g_b\rangle ,$ which therefore is not equal to $G,$ so no pairs of prime order elements generate $G.$

If $G$ does not have a generating pair of prime order elements, then for any two prime order elements $g_a,\, g_b,$ the subgroup they generate, $\langle g_a,g_b\rangle ,$ is a proper subgroup of $G.$ Hence, there is a path of length two between $A=\langle g_a\rangle $ and $B=\langle g_b\rangle $ in $\Delta _G$ and so, by Lemma 2.1, $\mathrm {diam}(\Delta _G)=2.$

Proof. First, note that $\mathrm {Aut}(S)$ is a split extension of $\mathrm {InnDiag}(S)$ by a group $\Phi _S\Gamma _S,$ where $\Phi _S$ and $\Gamma _S$ contain field and graph automorphisms, respectively. By [Reference Gorenstein, Lyons and Solomon14, Theorem 2.5.12, Definition 2.5.13], any nondiagonal outer automorphism $g$ of $S$ of odd prime order is a field automorphism, or $S\cong \mathrm {P}\Omega ^+_8(q)$ or ${}^3D_4(q)$ and $g$ is a graph or graph-field automorphism. In all cases, $g$ is conjugate to an element of $\Phi _S\Gamma _S$ .

Now, we show that for any two nondiagonal outer automorphisms $g_1$ and $g_2$ , there is a maximal parabolic subgroup $P$ such that both $g_1$ and $g_2$ normalise a conjugate of $P$ .

If $g_1$ and $g_2$ are field automorphisms, then, in particular, they are each conjugate to an element of $\Phi _S$ by [Reference Gorenstein, Lyons and Solomon14, Definition 2.5.13]. Now, $\Phi _S$ normalises a representative of each conjugacy class of parabolic subgroups of $S$ by [Reference Gorenstein, Lyons and Solomon14, Section 2.6], so the claim follows. If $g_1$ or $g_2$ are graph or graph-field automorphisms, then $S\cong \mathrm {P}\Omega ^+_8(q)$ or ${}^3D_4(q)$ and the parabolic maximal subgroup $P_2$ of $S$ is normalised by $\Gamma _S.$ Hence, $P_2$ is normalised by $\Phi _S\Gamma _S$ and, as all nondiagonal automorphisms are conjugate to an element of $\Phi _S\Gamma _S,$ it follows that $g_1$ and $g_2$ both normalise a conjugate of $P_2,$ as required.

Proof of Theorem 1.1.

By [Reference Csákány and Pollák8], if $\mathrm {diam}(\Delta _G)=4,$ then $G=S\rtimes C_p,$ where $S$ is a nonabelian simple group and $p$ is an odd prime.

Hence, $S$ cannot be a sporadic group or an alternating group with $n=5$ or $n\geq 7$ , since the outer automorphism group has size at most two in each case. If $S=A_6$ , then $|\mathrm {Out}(S)| = 4$ , so again there is no suitable $G$ . Therefore, $S$ is a group of Lie type. Write $G = S\rtimes \langle g \rangle $ , where $g$ has prime order $p$ .

Suppose that $A$ and $B$ are subgroups at distance 4 in $\Delta _G$ . By Lemma 2.1, we can assume that $A$ , $B$ are cyclic of prime order. First, suppose that $A$ or $B$ is a subgroup of $S$ . Without loss, we can assume $A\leq S.$ Since the graph is connected, $B$ is contained in a maximal subgroup of $G$ that has size strictly larger than $\vert B \vert ,$ so either $B$ is contained in $S$ or $B$ has order $p$ and is properly contained in a maximal subgroup $M_B$ of $G$ with $|M_B|>p.$ If $M_B$ and $S$ had a nontrivial intersection, then there would be a path between $A$ and $B$ of length 3, which contradicts our assumption that their distance is 4. Hence, we must have $|S\cap M_B| = 1$ . However, then $|SM_B| = |S||M_B|> p|S| = |G|$ , which is a contradiction. Hence, we can assume that neither $A$ nor $B$ is contained in $S$ and, hence, they both have order $p.$ We have several cases to consider.

The first case is when $G$ does not contain any diagonal automorphisms. By Lemma 2.3, $A$ and $B$ each normalise a conjugate of a fixed parabolic maximal subgroup $P<S$ and the normaliser of a parabolic subgroup is properly contained in $G$ .

Our second case is when $S=\mathrm {PSL}_n(q)$ such that $n$ is composite, and $A$ and $B$ are generated by diagonal automorphisms. Then, by [Reference Burness and Giudici4, Proposition 3.2.2], $A$ and $B$ each fix a $p$ -dimensional subspace of the natural module of $\mathrm {PSL}_n(q).$ In this case, the stabilisers of $p$ -dimensional subspaces are parabolic subgroups by [Reference Wilson22, Section 3.3.3], so $A$ and $B$ are contained in conjugate parabolic subgroups.

By [Reference Rekvényi18, Lemma 3.5], [Reference Gille and Guralnick13, Corollary 1.3] and [Reference Carter7, Theorem 2.8.7], the intersection of two conjugate parabolic subgroups is always nontrivial. Hence, in both of the above cases, there is a path of length at most $3$ between any two prime order subgroups of $G,$ so $\mathrm {diam}(\Delta _G)\leq 3.$

Our third case is $S=\mathrm {PSU}_n(q)$ with $n$ composite and $A$ , $B$ generated by diagonal automorphisms of order $p$ dividing $(n,q+1)$ . By [Reference Burness and Giudici4, Proposition 3.3.3], the preimage of each of these elements in $\mathrm {GU}_n(q)$ each fixes an orthogonal decomposition of the natural module into nondegenerate subspaces. Hence, each is contained in a maximal subgroup $M$ of $G$ whose preimage in $\mathrm {GU}_n(q)$ preserves an orthogonal decomposition of the natural module into two complementary nondegenerate subspaces of dimension $m$ and $n-m$ , respectively, for some $m$ with $1\leq m\leq n/2$ . By [Reference Kleidman and Liebeck16, Tables 2.1.C, 2.1.D, Lemma 4.1.1], we deduce that if $m<n/2$ , then $|M|>|G|^{1/2}$ . Therefore, if $A$ and $B$ are generated by elements that fix a decomposition of the natural module into a pair of nondegenerate subspaces of unequal dimension, then the maximal subgroups ${M_1\geq A}$ , $M_2\geq B$ of $G$ fixing these decompositions must have

$$ \begin{align*} |G|<|M_1||M_2| = |M_1M_2||M_1\cap M_2| \leq |G||M_1\cap M_2|. \end{align*} $$

This implies $|M_1\cap M_2|>1$ , so $A$ , $B$ are at distance 3 in $\Delta _G$ .

Finally, if $g$ is a diagonal automorphism of prime order $p$ whose preimage in $\mathrm {GU}_n(q)$ does not preserve a decomposition of the natural module into two nondegenerate subspaces of unequal dimension, then [Reference Burness and Giudici4, Proposition 3.3.3] implies that either $n$ is prime or $n=2p$ .

Proof of Theorem 1.2.

We begin by noting that $n \neq 5,7,13,17$ , since each can be written as $(q^d-1)/(q-1)$ for some prime power $q$ and positive integer $d\geq 2$ . We also note that $n=11$ is excluded by assumption (although we do deal with this case later in Lemma 3.1). Let $n=23.$ In this case, an element of order $23$ is only contained in two maximal subgroups that are both isomorphic to $M_{23}$ . Using GAP [21], we verify that subgroups generated by the $23$ -cycles

$$ \begin{align*} g_a & = (1,13,16,4,22,2,8,20,21,6,17,9,19,14,18,11,15,23,12,5,3,7,10),\\ g_b &= (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23) \end{align*} $$

are of distance $4$ by confirming that the $M_{23}$ maximal subgroups they are each contained in intersect trivially. Hence, $\mathrm {diam}(\Delta _{A_{23}})=4.$

For the remainder of the proof, we therefore suppose either $n=19$ or $n\geq 29$ .

Let $A = \langle g_a \rangle $ be a subgroup of size $n$ in $A_n$ . Note that every subgroup of $A_n$ of size $n$ is conjugate to $A$ , even though the same is not true for individual elements of order $n$ . Every maximal subgroup of $A_n$ containing $A$ must be transitive of prime degree. Thus, by the classification of transitive groups of prime degree [Reference Dixon and Mortimer9, page 99, Claims (i)–(v)], the only maximal subgroup of $G$ containing $A$ is $N_A = N_G(A) \cong n:{(n-1)}/{2}$ ; and the same is clearly true for any conjugate of $A$ . We will show that there exists $h \in A_n$ such that $N_A \cap N_A^h = 1$ , which implies that $A$ and $A^h$ are at distance 4 in the intersection graph for $A_n$ .

We proceed via a counting argument as in the proof of [Reference Cameron and Kantor6, Proposition 2.3]. The number of elements $h$ of $A_n$ such that $N_A \cap N_A^h \neq 1$ is at most the number of triples $(g_1,g_2,k)$ such that $g_1,g_2 \in N_A$ , $k \in A_n$ and $g_1^k = g_2$ . The number of such triples is at most $C\cdot |N_A|^2$ , where $C$ is the size of the largest centraliser amongst all nontrivial elements of $N_A$ . We find that

$$ \begin{align*} C\cdot |N_A|^2 \leq 2^{(n-1)/2} \bigg( \frac{n-1}{2}\bigg)!\cdot \bigg(\frac{n(n-1)}{2} \bigg)^2 < \frac{1}{n^2} |A_n| \end{align*} $$

when $n\geq 19$ . Hence, there exists $h\in A_n$ such that $N_A \cap N_A^h = 1$ and so the diameter of the intersection graph of $A_n$ is 4.

Proof. By Lemma 2.1 and [Reference Csákány and Pollák8, page 246], we can assume that if there exists a pair of subgroups at distance 4, then they are two cyclic groups $A$ , $B$ of order 11.

Every element of order 11 is contained in an $M_{11}$ and $|M_{11}|=7920$ . If $A$ and $B$ are at distance 4, then the $M_{11}$ (call them $H_1,H_2$ ) must meet only in the identity. However, $|H_1H_2|\geq |H_1||H_2|/|H_1\cap H_2| = |H_1||H_2| = 7920^2> |A_{11}|$ , which is a contradiction. So, $H_1$ and $H_2$ must intersect nontrivially, and $A$ and $B$ are at distance 3.

Proof. By Lemma 2.1 and [Reference Csákány and Pollák8, page 246], we can assume that if there exists a pair of subgroups at distance 4, then they are two cyclic groups $A$ , $B$ of order $n$ . For $n=5$ , the size of a maximal subgroup $M$ containing an $n$ -cycle is at least $10$ , and since $10^2> 60$ , these all need to intersect nontrivially, so there are no cyclic subgroups of order $n$ that are distance $4$ apart from each other. Similarly, for $n=7$ , if $M$ is a maximal subgroup containing an $n$ -cycle, then $\vert M \vert \geq 120$ and $120^2> {7!}/{2}$ so the diameter is again $3$ . For $n=13,$ we show using GAP [21] that the subgroups generated by ${g_a=(1,8,10,13,7,5,6,12,9,11,3,4,2)}$ and $g_b=(1,2,3,4,5,6,7,8,9,10,11,12,13)$ are of distance $4$ away from each other by intersecting the maximal subgroups they are contained in, so the diameter of the intersection graph is $4.$