\documentclass[a4paper,12pt]{article} \usepackage{e-jc} \specs{P1.21}{22(1)}{2015} \usepackage{amssymb, amsmath, amsthm, afterpage} \usepackage{amsfonts} \usepackage[dvips]{graphics} \usepackage{longtable} \usepackage{pdflscape} \usepackage{array} \usepackage[centerlast]{caption} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \setlength{\LTcapwidth}{5.8in} \newcolumntype{x}[1]{ >{\centering\hspace{0pt}}p{#1}} %\setlength\LTleft{0pt} %\setlength\LTright{0pt} \def\mathbi#1{\textbf{\em #1}} %\textheight 250mm %\textwidth 150mm %\oddsidemargin -5mm %\evensidemargin -5mm %\topmargin -20mm %\newcommand{\Label}[1]{\label{#1}\marginpar{\footnotesize #1} %\newcommand{\mybox}{\hfill $\square$} %\newcommand{\+}[1]{\ensuremath{\overset{+}{#1}}} %\newcommand{\pli}[1]{\ensuremath{\overset{+}{\imath}}} \newcommand{\mi}[1]{\ensuremath{\overset{-}{#1}}} \newcommand{\arb}[1]{\ensuremath{\overset{\pm}{#1}}} \newcommand{\C}{\ensuremath{\mathcal{C}}} \newcommand{\sym}{\ensuremath{\mathrm{Sym}}} \newcommand{\dih}{\ensuremath{\mathrm{Dih}}} \newcommand{\I}{\ensuremath{\mathcal{I}}} \newcommand{\J}{\ensuremath{\mathcal{J}}} \newcommand{\ip}[2]{\ensuremath{\langle{#1},{#2}\rangle}} %innerprod \newcommand{\eps}{\varepsilon} \newcommand{\G}{\ensuremath{\mathcal{G}}} \newcommand{\Z}{\ensuremath{\mathbb{Z}}} \newcommand{\droot}{\ensuremath{\Phi_{\mathrm{long}}}} \newcommand{\short}{\ensuremath{\Phi_{\mathrm{short}}}} \newcommand{\supp}{\ensuremath{\mathrm{supp}}} %\newcommand{\qed}{\hfill $\square$ \\} \newcommand{\ep}{\varepsilon} \newcommand{\thth}{^{{\scriptstyle\mathrm{th}}}} \newcommand{\nn}{\mathbb{N}} \newcommand{\zz}{\mathbb{Z}} \newcommand{\qq}{\mathbb{Q}} \newcommand{\rr}{\mathbb{R}} \newcommand{\cc}{\mathbb{C}} \newtheorem{thm}{Theorem}[section] \newtheorem{lemma}[thm]{Lemma} %and begin lemma etc for all this lot. \newtheorem{prop}[thm]{Proposition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{defn}[thm]{Definition} \newtheorem{cor}[thm]{Corollary} \newtheorem{rem}[thm]{Remark} \parindent 0pt %\newenvironment{proof}{\paragraph{Proof}}{\mybox} \newcommand{\RR}{\mathbb{R}} %and backslash R gets you the reals. \begin{document} \title{\bf On Commuting Graphs for Elements of Order $\boldsymbol{3}$\\ in Symmetric Groups} \author{Athirah Nawawi and Peter Rowley\\ \small School of Mathematics\\[-0.8ex] \small University of Manchester\\[-0.8ex] \small Manchester, M13 6PL, U.K.\\ \small \texttt{peter.j.rowley@manchester.ac.uk} } \date{\dateline{May 19, 2012}{Jan 20, 2015}{Feb 9, 2015}\\ \small Mathematics Subject Classifications: 05C25} \maketitle \begin{abstract} The commuting graph $\mathcal{C}(G,X)$, where $G$ is a group and $X$ is a subset of $G$, is the graph with vertex set $X$ and distinct vertices being joined by an edge whenever they commute. Here the diameter of $\mathcal{C}(G,X)$ is studied when $G$ is a symmetric group and $X$ a conjugacy class of elements of order $3$. \bigskip \noindent {\bf Keywords:} Commuting graph, Symmetric group, Order $3$ elements, Diameter \end{abstract} \section{Introduction}\label{intro} Suppose that $G$ is a finite group and $X$ is a subset of $G$. The {\em commuting graph} $\mathcal{C}(G,X)$ is the graph with $X$ as the vertex set and two distinct elements of $X$ being joined by an edge if they are commuting elements of $G$. This type of graph has been studied for a wide variety of groups $G$ and selection of subsets of $G$. One of the earliest investigations occurred in Brauer and Fowler \cite{BrauerFowler} in which $X = G \backslash \{1\}$. This particular case has recently been the subject of further study by Segev \cite{Segev1}, \cite{Segev2} and Segev and Seitz \cite{Segev3}. A great deal of attention has been focussed on the case when $X$ is a conjugacy class of involutions -- the so-called commuting involution graphs. Pioneering work on such graphs appeared in Fischer \cite{Fischer} which led to the construction of the three Fischer groups. Recently various properties of other commuting involution graphs have been studied; see, for example, \cite{BaBuPeRo1}, \cite{BaBuPeRo2}, \cite{BaBuPeRo3}, \cite{BaBuPeRo4}, \cite{Everett} and \cite{EverettRowley}. When $X$ is a conjugacy class of non-involutions, $\mathcal{C}(G,X)$ has to date received less attention. Never-the-less graphs of this type can be of interest -- witness the computer-free uniqueness proof of the Lyon's simple group by Aschbacher and Segev \cite{AschSeg} which employed a commuting graph whose vertex set consisted of the $3$-central subgroups of order $3$. Also see Baumeister and Stein \cite{BaumStein}, the results obtained there being used to describe the structure of Bruck loops and Bol loops of exponent $2$. Further, commuting graphs when $G$ is a symmetric group have been investigated in Bates, Bundy, Perkins and Rowley \cite{BaBuPeRo5} and Bundy\cite{Bundy}. The former paper concentrates on the structure of discs (around some fixed vertex) and the diameter of the graph while the latter gives a complete answer as to when $\mathcal{C}(G,X)$ is a connected graph.\\ In the present paper we shall determine the diameters of $\mathcal{C}(G,X)$ when $G$ is a symmetric group and $X$ is a $G$-conjugacy class of elements of order $3$. So for the rest of this paper we assume $G=Sym(\Omega) = Sym(n)$ with $G$ acting upon the set $\Omega=\{1,\dotsc,n\}$ in the usual manner. Also let \begin{equation} t=(1,2,3)(4,5,6)(7,8,9)\dotso(3r-2,3r-1,3r). \nonumber \end{equation} Thus $t$ has order $3$ and cycle type $1^{n-3r}3^r$. Set $X = t^G$, the $G$-conjugacy class of $t$, and let $\mathrm{Diam}$ $({\mathcal C} (G,X))$ denote the diameter of the commuting graph $\mathcal{C}(G,X)$. Our main results are as follows. \begin{thm} \label{Diam=2} If $n \geq 8r$, then $\mathrm{Diam}$ $({\cal C} (G,X))=2$. \end{thm} \begin{thm} \label{Diam=3} If $6r 1$ and $n=6r$, then $\mathrm{Diam}$ $({\cal C} (G,X)) \leq 4$. \end{thm} Consulting Table 1 (or Table 1 of \cite{BaBuPeRo5}) we see that for $r = 1, n = 7$ or $r = 2, n = 15$ we have that Diam $({\cal C} (G,X)) = 3$ and so Theorem \ref{Diam=2} is sharp. For $r = 2$ the same table gives Diam $({\cal C} (G,X)) = 4$ when $n = 12$ and $2$ when $n = 16$, so Theorems \ref{Diam=3} and \ref{Diamatmost4} are also sharp. We note that for $r = 1$ and $n = 6$, $\mathcal{C}(G,X)$ is disconnected which explains the assumption $ r > 1$ in Theorem \ref{Diamatmost4}. All the graphs we consider here are connected -- see \cite{Bundy}. For $g \in G$, $supp(g)$ denotes the set of points of $\Omega$ not fixed by $g$. We use $d(,)$ for the usual distance metric on the graph ${\cal C} (G,X)$. For $x \in X$, the $i^{th}$ disc, $\Delta_i(x)$, is defined as follows \begin{equation} \Delta_i(x) = \{y \mid y \in X \mbox{and} \; d(x,y) = i \}. \nonumber \end{equation} The proofs of Theorems \ref{Diam=2}, \ref{Diam=3} and \ref{Diamatmost4} adopt a similar, somewhat direct, approach. Since $G$ acting by conjugation upon $X$ induces graph automorphisms on ${\cal C} (G,X)$ and of course is transitive on $X$, it suffices to determine (or bound) $d(t,x)$ for an arbitrary vertex $x$ of $X$. This we do by writing down explicit paths in ${\cal C} (G,X)$. \section{Diameter of $\mathcal{C}(G,X)$}\label{Diameters} We begin by establishing Theorem \ref{Diam=2}.\\ \textbf{Proof of Theorem 1.1} \mbox{}\\ Let $x \in X$. Set $\Lambda=supp(t) \cup supp(x)$ and $s=|supp(t) \cap supp(x)|$. Then $|\Lambda|=6r-s$. If $s \geq r$, then $|\Lambda| \leq 5r$. Hence there exists $y \in X$ with $supp(t) \cap supp(y)=\emptyset=supp(x) \cap supp(y)$ and so $d(t,x) \leq 2$. Now consider the case $s < r$, and set $e=r-s$. Without loss of generality we may suppose that $supp(t) \cap supp(x) \subseteq \{1,2,3,\dotsc,3s-2,3s-1,3s\}$. Put $y_1=(3s+1,3s+2,3s+3) \dotso (3r-2,3r-1,3r)$ (so $y_1$ is the product of the ``last'' $r-s=e$ 3-cycles of $t$). Since $|\Omega \setminus \Lambda|=8r-(6r-s)=2r+s > 3s$ and $s < r$, we may select $y_2$ with $supp(y_2) \subseteq \Omega \setminus \Lambda$ and $y_2$ is a product of $s$ pairwise disjoint 3-cycles. So $y=y_1y_2 \in X$, $ty=yt$ and $xy=yx$. Thus $d(t,x) \leq 2$. Clearly $\mathrm{Diam}$ $({\cal C} (G,X)) \geq 2$, and so the theorem follows.\\ Before proving Theorems \ref{Diam=3} and \ref{Diamatmost4} we introduce some notation and certain permutations of $Sym(\Omega)$. These permutations, though elements of order $3$, are not in general in $X$. We will assume that $|\Omega| \geq 6r$. For $x \in X$, we let $\{\vartheta_i(x)\}_{i=1, \dotsc, r}$ denote the orbits of $\langle x \rangle$ on $\Omega$ of size 3. So $supp(x)=\bigcup_{i=1}^r \vartheta_i(x)$. Write $t=t_1t_2 \dotso t_r$ where $t_i=(3i-2,3i-1,3i)$. So $\vartheta(t_i)=\vartheta_i(t)=\{3i-2,3i-1,3i\}$.\\ Let $x \in X$. Denote the product of the $t_i$'s for which $\vartheta_i(t) \cap supp(x)=\emptyset$ by $\tau_0$ and let $\tau_3$ be the product of the $t_i$'s for which $\vartheta_i(t) \subseteq supp(x)$. Also let $\tau_1$ be the product of $r_1$ $t_i$'s where $| \vartheta_i(t) \cap supp(x) |=1$, $3 \mid r_1$ and $r_1$ is as large as possible. Analogously, $\tau_2$ is the product of $r_2$ $t_i$'s where $| \vartheta_i(t) \cap supp(x) |=2$, $3 \mid r_2$ and $r_2$ is as large as possible. Setting $\tau_*=t\tau_0^{-1}\tau_1^{-1}\tau_2^{-1}\tau_3^{-1}$ we have $t=\tau_*\tau_0\tau_1\tau_2\tau_3$. Let $r_*$ be the number of $t_i$'s in $\tau_*$, $r_0$ the number of $t_i$'s in $\tau_0$ and $r_3$ the number of $t_i$'s in $\tau_3$. Observe that the maximality of $r_1$ and $r_2$ means $r_* \leq 4$ and that at most two of the $t_i$'s in $\tau_*$ will have $| \vartheta_i(t) \cap supp(x) |=1$ and at most two will have $| \vartheta_i(t) \cap supp(x) |=2$. Evidently $r=r_*+r_0+r_1+r_2+r_3$ and, for $i=0,1,2,3,| supp(x) \cap supp(\tau_i) |=ir_i$. Putting $s_*=| supp(x) \cap supp(\tau_*) |$, we also have \begin{equation} | supp(t) \cap supp(x) |=s_*+r_1+2r_2+3r_3. \nonumber \end{equation} Set $\Lambda=\Omega \setminus (supp(t) \cup supp(x))$. Since \begin{align*} | supp(t) \cup supp(x) |&=3r+3r-(s_*+r_1+2r_2+3r_3) \\ &=6r-(s_*+r_1+2r_2+3r_3) \end{align*} it follows that \begin{equation} | \Lambda | = s_*+r_1+2r_2+3r_3 \;\mbox{if}\; n = 6r \;\mbox{and} \nonumber \end{equation} \begin{equation} | \Lambda | \geq 1+s_*+r_1+2r_2+3r_3 \;\mbox{if}\; n > 6r. \nonumber \end{equation} Since 3 divides $r_1$, we may write \begin{equation} \tau_1=\prod \mu_{i_1i_2i_3} \nonumber \end{equation} where the product of the $\mu_{i_1i_2i_3}=t_{i_1}t_{i_2}t_{i_3}$ is pairwise disjoint. For each $\mu_{i_1i_2i_3}=t_{i_1}t_{i_2}t_{i_3}=(3i_1-2,3i_1-1,3i_1)(3i_2-2,3i_2-1,3i_2)(3i_3-2,3i_3-1,3i_3)$ we may without loss, suppose that $supp(\mu_{i_1i_2i_3}) \cap supp(x)=\{3i_1-2,3i_2-2,3i_3-2\}$. Put \begin{equation} \lambda_{i_1i_2i_3}=(3i_1-2,3i_2-2,3i_3-2)(3i_1-1,3i_2-1,3i_3-1)(3i_1,3i_2,3i_3). \nonumber \end{equation} Then $\lambda_{i_1i_2i_3}$ commutes with $\mu_{i_1i_2i_3}$. Let \begin{equation} \rho_1=\prod \lambda_{i_1i_2i_3} \nonumber \end{equation} and observe that $\rho_1$ commutes with $t$ and will be a pairwise disjoint product of $r_1$ 3-cycles. Further, $\frac{r_1}{3}$ of the 3-cycles in $\rho_1$ will have their support contained in $supp(x)$ while the remaining $\frac{2r_1}{3}$ 3-cycles in $\rho_1$ will have their support intersecting $supp(x)$ in the empty set. Also, as 3 divides $r_2$, we may express \begin{equation} \tau_2=\prod \eta_{j_1j_2j_3} \nonumber \end{equation} where $\eta_{j_1j_2j_3}=t_{j_1}t_{j_2}t_{j_3}$ with the product being pairwise disjoint. For each $\eta_{j_1j_2j_3}$ we may suppose that $supp(\eta_{j_1j_2j_3}) \cap supp(x)=\{3j_1-2,3j_1-1,3j_2-2,3j_2-1,3j_3-2,3j_3-1\}$. Define \begin{equation} \delta_{j_1j_2j_3}=(3j_1,3j_2,3j_3)(3j_1-2,3j_2-2,3j_3-2)(3j_1-1,3j_2-1,3j_3-1), \nonumber \end{equation} and let \begin{equation} \rho_2=\prod \delta_{j_1j_2j_3}. \nonumber \end{equation} Evidently $\rho_2$ commutes with $t$ and $\rho_2$ is a pairwise disjoint product of $r_2$ 3-cycles. Moreover, $\frac{2r_2}{3}$ of the 3-cycles in $\rho_2$ will have their support contained in $supp(x)$ and the remaining $\frac{r_2}{3}$ have supports intersecting $supp(x)$ in the empty set. Let $\sigma_1$ (respectively $\sigma_2$) be the product of the $\frac{2r_1}{3}$ (respectively $\frac{r_2}{3}$) 3-cycles in $\rho_1$ (respectively $\rho_2$) whose support intersects $supp(x)$ in the empty set. Also let $\sigma_4$ be a pairwise disjoint product of ($\frac{r_1}{3}+\frac{2r_2}{3}+r_3$) 3-cycles with $supp(\sigma_4) \subseteq \Lambda$. Put $\Delta=\Lambda \backslash supp(\sigma_4)$.\\ We now summarize the pertinent properties of the permutations just introduced. \begin{lemma} \label{Lem1} \begin{trivlist} \item{(\textit{i})} $supp(\tau_0\rho_1\rho_2\tau_3) \subseteq supp(t)$, $\tau_0\rho_1\rho_2\tau_3$ commutes with $t$ and is the product of $r - r_*$ pairwise disjoint $3$-cycles. \item{(\textit{ii})} $\sigma_1\sigma_2\tau_0\sigma_4$ commutes with $\tau_0\rho_1\rho_2\tau_3$ and is the product of $r - r_*$ pairwise disjoint $3$-cycles. Moreover $supp(\sigma_1\sigma_2\tau_0\sigma_4) \cap supp(x) = \emptyset$. \item{(\textit{iii})} $|\Delta| = s_* $ if $n = 6r$ and $|\Delta| \geq 1 + s_* $ if $n \geq 6r$. \end{trivlist} \end{lemma} \begin{proof} (i) Since $supp(\rho_1\rho_2) = supp(\tau_1\tau_2)$, $\tau_0\rho_1\rho_2\tau_3$ is the product of pairwise disjoint $3$-cycles, and the number of such $3$-cycles is $r - r_*$. Because $\rho_1$ and $\rho_2$ both commute with $t$, $\tau_0\rho_1\rho_2\tau_3$ commutes with $t$.\\ (ii) Since $supp(\sigma_4) \subseteq \Delta$ and $supp(\tau_0\rho_1\rho_2\tau_3) \subseteq supp(t)$, $\sigma_4$ commutes with $\tau_0\rho_1\rho_2\tau_3$. While $\sigma_1\sigma_2\tau_0$ is a product of $3$-cycles which appear in $\tau_0\rho_1\rho_2\tau_3$ and therefore $\sigma_1\sigma_2\tau_0\sigma_4$ commutes with $\tau_0\rho_1\rho_2\tau_3$. By construction $\sigma_i \cap supp(x) = \emptyset (i = 1,2)$, $supp(\tau_0) \cap supp(x) = \emptyset$ by definition and because we chose $\sigma_4$ so as $supp(\sigma_4) \subseteq \Lambda$ we get $supp(\sigma_1\sigma_2\tau_0\sigma_4) \cap supp(x) = \emptyset$.\\ (iii) Part (iii) follows from $|supp(\sigma_4)| = r_1 + 2r_2 + 3r_3$ and $\Delta = \Lambda \backslash supp(\sigma_4)$. \end{proof} We are now in a position to prove Theorem \ref{Diam=3}.\\ \begin{proof}[\emph{\bf Proof of Theorem 1.2}]\ Let $y \in X$ be such that $| supp(y) \cap \vartheta_i(t) | = 1 = | supp(t) \cap \vartheta_i(y) |$ for $i=1,\dotsc,r$. Then $C_G(t) \cap C_G(y) = Sym(\Psi)$ where $\Psi=\Omega \setminus (supp(t) \cup supp(y))$. Now $| supp(t) \cup supp(y) | = 3r+3r-r=5r$ and so $| \Psi | = n-5r < 8r-5r=3r$. Thus $X \cap C_G(t) \cap C_G(y)=\emptyset$ and consequently $d(t,y) \geq 3$. Hence Diam $({\cal C} (G,X)) \geq 3$.\\ Let $x \in X$. We aim to show that $d(t,x) \leq 3$. On account of $C_G(t)$ having shape $3^r Sym(r) \times Sym(n-3r)$ there is no loss in supposing $\tau_*=t_1 \dotso t_{r_*}$ where $0 \leq r_* \leq 4$ ($r_*=0$ meaning $\tau_*=1$). Depending on $\tau_*$ we define two elements $\rho_*$ and $\sigma_*$ which will be the product of $r_*$ pairwise disjoint 3-cycles.\\ $\mathbf{(1)}$ $\mbox{}r_*=4$\\ Then we have $\tau_*=t_1t_2t_3t_4=(1,2,3)(4,5,6)(7,8,9)(10,11,12)$, $s_*=6$ and we may, without loss, assume $supp(\tau_*) \cap supp(x)=\{1,4,7,8,10,11\}$. Observe that $|supp(x) \backslash supp(t)| \geq 6$ and so we may select $\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5,\alpha_6 \in supp(x) \backslash supp(t)$. Also by Lemma \ref{Lem1}(iii), as $s_*=6$, $|\Delta| \geq 7$. Thus we may also select $\beta_1,\beta_2,\beta_3,\beta_4,\beta_5,\beta_6 \in \Delta$. Define \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\alpha_4,\alpha_5,\alpha_6)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6) \nonumber \end{equation} and \begin{equation} \sigma_*=(2,3,5)(6,9,12)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6). \nonumber \end{equation} $\mathbf{(2)}$ $\mbox{}r_*=3$\\ So $\tau_*=t_1t_2t_3=(1,2,3)(4,5,6)(7,8,9)$. First we examine the case when $s_*=4$, and may suppose that $supp(\tau_*) \cap supp(x)=\{1,4,7,8\}$. Here we have $|supp(x) \backslash supp(t)| \geq 5$ and $|\Delta| \geq 5$. Choose $\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2,\beta_3,\beta_4,\beta_5 \in \Delta$, and define \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\alpha_4,\alpha_5,\beta_1)(\beta_2,\beta_3,\beta_4) \nonumber \end{equation} and \begin{equation} \sigma_*=(2,3,5)(6,9,\beta_5)(\beta_2,\beta_3,\beta_4). \nonumber \end{equation} We move onto the case when $s_*=5$ and, without loss of generality, assume $supp(\tau_*) \cap supp(x)=\{1,2,4,5,7\}$. Since $|supp(x) \backslash supp(t)| \geq 4$ and $|\Delta| \geq 6$, we may select $\alpha_1,\alpha_2,\alpha_3 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2,\beta_3,\beta_4,\beta_5,\beta_6 \in \Delta$. Then we take \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6) \nonumber \end{equation} and \begin{equation} \sigma_*=(3,6,8)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6). \nonumber \end{equation} %\clearpage $\mathbf{(3)}$ $\mbox{}r_*=2$\\ So $\tau_*=t_1t_2=(1,2,3)(4,5,6)$ with $s_*=2$, 3 or 4. First we look at the case when $s_*=2$ or 3. Then we have $|supp(x) \backslash supp(t)| \geq 3$, $|supp(t) \backslash supp(x)| \geq 3$ and $|\Delta| \geq 3$. Choosing $\alpha_1,\alpha_2,\alpha_3 \in supp(x) \backslash supp(t)$, $\beta_1,\beta_2,\beta_3 \in \Delta$ and $\gamma_1,\gamma_2,\gamma_3 \in supp(t) \backslash supp(x))$, we let \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\beta_1,\beta_2,\beta_3) \nonumber \end{equation} and \begin{equation} \sigma_*=(\gamma_1,\gamma_2,\gamma_3)(\beta_1,\beta_2,\beta_3). \nonumber \end{equation} Now assume that $s_*=4$, and, without loss, that $supp(\tau_*) \cap supp(x)=\{1,2,4,5\}$. Because $|supp(x) \backslash supp(t)| \geq 2$ and $|\Delta| \geq 5$ we may choose $\alpha_1,\alpha_2 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2,\beta_3,\beta_4,\beta_5 \in \Delta$ and then define \begin{equation} \rho_*=(\alpha_1,\alpha_2,\beta_1)(\beta_2,\beta_3,\beta_4) \nonumber \end{equation} and \begin{equation} \sigma_*=(3,6,\beta_5)(\beta_2,\beta_3,\beta_4). \nonumber \end{equation} $\mathbf{(4)}$ $\mbox{}r_*=1$\\ Then $\tau_*=t_1=(1,2,3)$ and $s_*=1$ or 2. Suppose $s_*=1$ with $supp(\tau_*) \cap supp(x)=\{1\}$. So $|supp(x) \backslash supp(t)| \geq 2 \leq |\Delta|$. Selecting $\alpha_1,\alpha_2 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2 \in \Delta$, we set \begin{equation} \rho_*=(\alpha_1,\alpha_2,\beta_1) \nonumber \end{equation} and \begin{equation} \sigma_*=(2,3,\beta_2). \nonumber \end{equation} While if $s_*=2$, then $|\Delta| \geq 3$ and selecting $\beta_1,\beta_2,\beta_3 \in \Delta$ we set \begin{equation} \rho_*=\sigma_*=(\beta_1,\beta_2,\beta_3). \nonumber \end{equation} $\mathbf{(5)}$ $\mbox{}r_*=0$\\ Here we take $\rho_*=1=\sigma_*$.\\ Put $y=\rho_*\tau_0\rho_1\rho_2\tau_3$. Since $y$ is the product of $r_*+r_0+r_1+r_2+r_3=r$ disjoint 3-cycles, $y \in X$. Further we have that $ty=yt$ by Lemma \ref{Lem1}(i). Next we consider $z=\sigma_*\sigma_1\sigma_2\tau_0\sigma_4$. Each of $\sigma_*\sigma_1,\sigma_2,\tau_0$ and $\sigma_4$ are pairwise disjoint. Recalling that $\sigma_1,\sigma_2$ and $\sigma_4$ are, respectively, the product of $\frac{2r_1}{3},\frac{r_2}{3},(\frac{r_1}{3}+\frac{2r_2}{3}+r_3)$ disjoint 3-cycles, we see that $z \in X$. It may be further checked using Lemma \ref{Lem1}(ii) that $yz=zy$ and $xz=zx$, and consequently $d(t,x) \leq 3$. This completes the proof of Theorem \ref{Diam=3}. \end{proof} \begin{proof}[\emph{\bf Proof of Theorem 1.3}]\ Let $x \in X$. Our objective here is to show that $d(t,x) \leq 4$ from which it will follow that Diam $({\cal C} (G,X)) \leq 4$. We proceed in a similar fashion to that in the proof of Theorem \ref{Diam=2} though here, except for some cases, we will define three permutations $\rho_*, \sigma_*, \xi_*$, each a product of $r_*$ pairwise disjoint cycles.\\ $\mathbf{(6)}$ $\mbox{}r_*=4$\\ So $\tau_*=t_1t_2t_3t_4=(1,2,3)(4,5,6)(7,8,9)(10,11,12)$ with $s_*=6$. Assume, without loss, that $supp(\tau_*) \cap supp(x)=\{1,4,7,8,10,11\}$. Since $|supp(x) \backslash$ $supp(t)| \geq 6$ and so we may choose $\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5,\alpha_6 \in supp(x) \backslash supp(t)$. Further, as $|\Delta| = s_* = 6$ by Lemma \ref{Lem1}(iii), we may also choose $\beta_1,\beta_2,\beta_3,\beta_4,$ $\beta_5,\beta_6 \in \Delta$. Now define \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\alpha_4,\alpha_5,\alpha_6)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6) \nonumber \end{equation} and \begin{equation} \sigma_*=(2,3,5)(6,9,12)(\beta_1,\beta_2,\beta_3)(\beta_4,\beta_5,\beta_6). \nonumber \end{equation} $\mathbf{(7)}$ $\mbox{}r_*=3$\\ So $\tau_*=t_1t_2t_3=(1,2,3)(4,5,6)(7,8,9)$. If $s_*=4$ we may suppose without loss that $supp(\tau_*) \cap supp(x)=\{1,4,7,8\}$. Here we have $|supp(x) \backslash supp(t)| \geq 5$ and $|\Delta| = s_* = 4$ by Lemma \ref{Lem1}(iii). Choose $\alpha_1,\alpha_2,\alpha_3 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2,\beta_3\in \Delta$, and define \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\beta_1,\beta_2,\beta_3)(1,2,3), \nonumber \end{equation} \begin{equation} \sigma_*=(5,6,9)(\beta_1,\beta_2,\beta_3)(1,2,3) \nonumber \end{equation} and \begin{equation} \xi_*=(5,6,9)(\beta_1,\beta_2,\beta_3)(\alpha,\beta,\gamma), \nonumber \end{equation} where $(\alpha,\beta,\gamma)$ is a $3$-cycle of $x$ for which $1 \notin \{\alpha,\beta,\gamma \}$. Note that $\{\alpha,\beta,\gamma \} \cap supp(\sigma_*) = \emptyset$. For the case when $s_*=5$, without loss of generality, we assume $supp(\tau_*) \cap supp(x)=\{1,4,5,7,8\}$. Since $|supp(x) \backslash supp(t)| \geq 4$ and $|\Delta| = s_* = 5$, we may select $\alpha_1,\alpha_2,\alpha_3 \in supp(x) \backslash supp(t)$ and $\beta_1,\beta_2,\beta_3 \in \Delta$. Then we take \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\beta_1,\beta_2,\beta_3)(4,5,6), \nonumber \end{equation} \begin{equation} \sigma_*=(2,3,9)(\beta_1,\beta_2,\beta_3)(4,5,6) \nonumber \end{equation} and \begin{equation} \xi_*=(2,3,9)(\beta_1,\beta_2,\beta_3)(\alpha,\beta,\gamma), \nonumber \end{equation} where $(\alpha,\beta,\gamma)$ is a $3$-cycle of $x$ chosen so as $\{4,5\} \cap \{\alpha,\beta,\gamma \} = \emptyset$. Since $r \geq r_* = 3$ such a choice is possible.\\ Before dealing with $r_* = 2$ we analyze a number of small cases.\\ $\mathbf{(8)}$ $\mbox{}$ Suppose that $t = (1,2,3)(4,5,6)$ (so $r = 2$ and $n = 12$). \begin{trivlist} \item{(\textit{i})} If $x = (1,7,8)(4,9,10)$ or $x = (1,4,7)(2,5,8)$, then $d(t,x) \leq 4$. \item{(\textit{ii})}If $x = (1,4,7)(8,9,10)$, then $d(t,x)\leq 3$. \end{trivlist} Assume that $x = (1,7,8)(4,9,10)$, and let \[ x_1 = (7,8,11)(9,10,12),\quad x_2 = (2,3,5)(9,10,12),\quad x_3 = (2,3,5)(1,7,8).\] Then $x_1, x_2, x_3 \in X$ and $(t,x_1, x_2, x_3,$ $x)$ is a path in $\mathcal{C}(G,X)$ whence $d(t,x) \leq 4$. In the case $x = (1,4,7)(2,5,8)$ we take $x_1 = (7,8,9)(10,11,12), x_2 = (1,3,6)(10,11,12)$ and $x_3 = (2,5,8)$ $(10,11,12)$. It is easily checked that $(t,x_1,x_2,x_3,x)$ is also a path in $\mathcal{C}(G,X)$, so proving part (i). For $x = (1,4,7)(8,9,10)$ taking $x_1 = (1,2,3)(8,9,10)$ and $x_2 = (5,6,11)(8,9,10)$ gives a path $(t,x_1,x_2,x)$ in $\mathcal{C}(G,X)$. So (ii) holds and (8) is proved.\\ $\mathbf{(9)}$ $\mbox{}$ Suppose $t = (1,2,3)(4,5,6)(7,8,9)$ with $\tau_* = (1,2,3)(4,5,6)$ (so $r = 3$ and $n = 18$). Let $x \in X$ be such that $supp(\tau_*) \cap supp(x) = \{1,4\}$ and assume $1$ and $4$ are in different $3$-cycles of $x$. Then $d(t,x) \leq 4$.\\ By assumption $x = (1,*,*)(4,\delta,\epsilon)(\alpha,\beta,\gamma)$ with $\{1,4\} \cap \{\alpha,\beta,\gamma\} = \emptyset$. Because $\tau_* = (1,2,3)(4,5,6)$ we must have $supp(t) \cap supp(x) = \{1,4\}$ or $\{1,4,7,8,9\}$. Suppose the former holds and set $x_1 = (1,2,3)(\alpha,\beta,\gamma)(7,8,9)$ and $x_2 = (4,\delta,\epsilon)(\alpha,\beta,\gamma)(7,8,9)$. Then $(t,x_1,x_2,x)$ is a path in $\mathcal{C}(G,X)$. Hence $d(t,x) \leq 3$. Turning to the latter case we have $|supp(t) \cup supp(x)| = 13$. So we may choose, say, $16,17,18 \in \Lambda$ and then take $x_1 = (1,2,3)(4,5,6)$ $(16,17,18), x_2 = (1,2,3)(\alpha,\beta,\gamma)(16,17,18)$ and $x_3 = (4,\delta,\epsilon)(\alpha,\beta,\gamma)(16,17,$ $18)$, giving a path $(t,x_1,x_2,x_3,x)$ in $\mathcal{C}(G,X)$. Thus $d(t,x) \leq 4$, so proving (9).\\ $\mathbf{(10)}$ $\mbox{}r_*=2$\\ So we have $\tau_* = t_1t_2 =(1,2,3)(4,5,6)$ with $s_* = 2, 3$ or $4$. First we consider the case $s_* = 2$, and assume $supp(\tau_*) \cap supp(x) = \{1,4\}$. For the moment also assume that $r = 2$ (so $t = \tau_*$). Then, without loss, $x$ is either $(1,7,8)(4,9,10)$ ($1$ and $4$ in different $3$-cycles of $x$) or $(1,4,7)(8,9,10)$ ($1$ and $4$ in the same $3$-cycle of $x$). By (8)(i) we have $d(t,x) \leq 4$. So, since we are aiming to show that $d(t,x) \leq 4$, we may suppose $r \geq 3$. Now consider the possibility that $r = 3$ and $1$ and $4$ are in different $3$-cycles of $x$. Then, without loss, $x = (1,*,*)(4,\delta,\epsilon)(\alpha,\beta,\gamma)$ in which case $d(t,x) \leq 4$ by (9). Thus, when $r = 3$, we may suppose $1$ and $4$ are in the same $3$-cycle of $x$. Consequently, as $r \geq 3$, we may find two $3$-cycles of $x$, $(\alpha,\beta,\gamma)$ and $(\delta,\epsilon,\lambda)$ such that $\{\alpha,\beta,\gamma,\delta,\epsilon,\lambda\} \cap \{1,4\} = \emptyset$. Now we define $\rho_*, \sigma_*$ and $\xi_*$ by taking $\rho_* = \sigma_* = \tau_*$ and $\xi_* = (\alpha,\beta,\gamma), (\delta,\epsilon,\lambda)$.\\ Next we look at the case $s_* = 3$. Then we have $|supp(x) \backslash supp(t)| \geq 3$, $|supp(t) \backslash supp(x)| \geq 3$ and $|\Delta| = s_* = 3$. Choosing $\alpha_1,\alpha_2,\alpha_3 \in supp(x) \backslash$ $supp(t)$, $\beta_1,\beta_2,\beta_3 \in \Delta$ and $\gamma_1,\gamma_2,\gamma_3 \in supp(t) \backslash supp(x))$, we let \begin{equation} \rho_*=(\alpha_1,\alpha_2,\alpha_3)(\beta_1,\beta_2,\beta_3) \nonumber \end{equation} and \begin{equation} \sigma_*=(\gamma_1,\gamma_2,\gamma_3)(\beta_1,\beta_2,\beta_3). \nonumber \end{equation} Finally we come to $s_* = 4$. So without loss we have $supp(\tau_*) \cap supp(x) = \{1,2,4,5\}$. Suppose, for the moment, that for all $3$-cycles $(\alpha,\beta,\gamma)$ we have $\{1,2\} \cap \{\alpha,\beta,\gamma\} \neq \emptyset \neq \{4,5\} \cap \{\alpha,\beta,\gamma\}$. Then it follows that $r = 2$ and, without loss, $x = (1,4,7)(2,5,8)$. But then $d(t,x) \leq 4$ by (8)(ii). Thus we may suppose $x$ contains a $3$-cycle $(\alpha,\beta,\gamma)$ such that $(\alpha,\beta,\gamma) \cap \{1,2\} = \emptyset$, and we can now define $\rho_*$ and $\sigma_*$. Since $|\Delta| = s_* = 4$, we have $\beta_1,\beta_2,\beta_3 \in \Delta$. Let $\rho_* = (1,2,3)(\beta_1,\beta_2,\beta_3)$ and $\sigma_* = (\alpha,\beta,\gamma)(\beta_1,\beta_2,\beta_3)$. This completes the case $s_* = 4$ and (10).\\ Yet another special case must be looked at before doing $r_* = 1$.\\ $\mathbf{(11)}$ $\mbox{}$ Let $t = (1,2,3)(4,5,6)$ with $\tau_* = (1,2,3)$. Suppose $x = (1,*,*)(2,*,*)$ $\in X$ with $supp(\tau_*) \cap supp(x) = \{1,2\}$. Then $d(t,x) \leq 3$.\\ Since $\tau_* = (1,2,3)$, $supp(t) \cap supp(x) = \{1,2\}$ or $\{1,2,4,5,6\}$. If $supp(t) \cap supp(x) = \{1,2\}$ and, say $\Omega \backslash (supp(t) \cap supp(x))= \{11,12\}$, then define $x_1 = (4,5,6)(10,11,12), x_2 = (4,5,6)(\alpha,\beta,\gamma)$ where $(\alpha,\beta,\gamma)$ is a $3$-cycle not containing $10$. While in the other case with, say $\Omega \backslash (supp(t) \cap supp(x))= \{8,9,10,11,12\}$ we define $x_1 = (8,9,10)(7,11,12), x_2 = (8,9,10)(\alpha,\beta,\gamma)$ where $(\alpha,\beta,\gamma)$ is a $3$-cycle not containing $7$. Hence $d(t,x) \leq 3$.\\ $\mathbf{(12)}$ $\mbox{} r_* = 1$\\ So we have either, without loss, $supp(\tau_*) \cap supp(x) = \{1\}$ or $\{2,3\}$. In view of (10), as $r > 1$, either $d(t,x) \leq 3$ or we may find a $3$-cycle $(\alpha,\beta,\gamma)$ of $x$ for which $supp(\tau_*) \cap \{\alpha,\beta,\gamma\} = \emptyset$. In the latter case we define $\rho_* = \sigma_* = \tau_*$ and $\xi_* = (\alpha,\beta,\gamma)$.\\ $\mathbf{(13)}$ $\mbox{} r_* = 0$\\ Just as in (5) we take $\rho_* = 1 = \sigma_*$. Now let $y = \rho_*\tau_0\rho_1\rho_2\tau_3, z = \sigma_*\sigma_1\sigma_2\tau_0\sigma_4$ and $w = \xi_*\sigma_1\sigma_2\tau_0\sigma_4$ (where $w$ is only defined if in (6), (7), (10), (12), (13) $\xi_*$ is defined). Then $y,z,w \in X$ with $(t,y,z,w,x)$ is a path in $\mathcal{C}(G,X)$. Consequently $d(t,x) \leq 4$. Since $x$ was an arbitrary vertex, this shows that $\mathrm{Diam}$ $(\mathcal{C}(G,X)) \leq 4$ and completes the proof of Theorem \ref{Diamatmost4}. \end{proof} We end this paper with a table containing some calculations on diameters and discs using \textsc{Magma}\cite{magma}. Each entry in the table first gives the size of the relevant $\Delta_i(t)$ for the given $r$ and $n$ with the number in brackets being the number of $C_G(t)$-orbits on $\Delta_i(t)$. A blank entry means that $|\Delta_i(t)| = 0$. \begin{landscape} \centering \begin{longtable}{|l|x{2.1cm}|x{3.0cm}|x{3.5cm}|x{4.0cm}|x{3.3cm}|x{2.3cm}|} \hline & ${\Delta}_1(t)$ & ${\Delta}_2(t)$ & ${\Delta}_3(t)$ & ${\Delta}_4(t)$ & ${\Delta}_5(t)$ & ${\Delta}_6(t)$ \tabularnewline \hline \endfirsthead \multicolumn{7}{c}{{\tablename} \thetable{} -- Continued} \\[0.5ex] \hline & ${\Delta}_1(t)$ & ${\Delta}_2(t)$ & ${\Delta}_3(t)$ & ${\Delta}_4(t)$ & ${\Delta}_5(t)$ & ${\Delta}_6(t)$ \tabularnewline \hline \endhead \multicolumn{7}{r}{{Continued on Next Page\ldots}} \tabularnewline \endfoot \hline \caption{Disc sizes and $C_G(t)$-orbits \label{Table1}} \tabularnewline \endlastfoot $\mathbi{r=1}$ & & & & & & \tabularnewline $n=7$ & 9 (2) & 24 (2) & 36 (1) & - & - & - \tabularnewline $n=8$ & 21 (2) & 90 (3) & - & - & - & - \tabularnewline $n=9$ & 41 (2) & 126 (3) & - & - & - & - \tabularnewline \hline \hline $\mathbi{r=2}$ & & & & & & \tabularnewline $n=10$ & 35 (4) & 192 (6) & 1,008 (10) & 2,628 (20) & 3,672 (13) & 864 (5) \tabularnewline $n=11$ & 83 (4) & 1,080 (9) & 7,560 (23) & 9,756 (23) & - & - \tabularnewline $n=12$ & 203 (5) & 6,300 (16) & 28,296 (34) & 2,160 (5) & - & - \tabularnewline $n=13$ & 563 (5) & 25,740 (30) & 42,336 (25) & - & - & - \tabularnewline $n=14$ & 1,571 (5) & 67,140 (48) & 51,408 (7) & - & - & - \tabularnewline $n=15$ & 4,035 (5) & 168,948 (54) & 27,216 (1) & - & - & - \tabularnewline $n=16$ & 9,363 (5) & 310,956 (55) & - & - & - & - \tabularnewline \hline \hline $\mathbi{r=3}$ & & & & & & \tabularnewline $n=9$ & 25 (4) & 216 (4) & 1,512 (11) & 486 (6) & - & - \tabularnewline $n=12$ & 49 (7) & 648 (8) & 9,936 (39) & 90,990 (139) & 327,024 (404) & 64,152 (102) \tabularnewline $n=13$ & 121 (7) & 2,808 (18) & 79,488 (85) & 724,086 (383) & 783,432 (332) & 11,664 (3) \tabularnewline $n=14$ & 265 (7) & 9,936 (23) & 390,582 (138) & 3,217,806 (564) & 865,890 (143) & - \tabularnewline $n=15$ & 745 (9) & 62,424 (46) & 2,414,610 (243) & 8,733,420 (594) & - & - \tabularnewline $n=16$ & 2,545 (9) & 482,760 (90) & 17,798,778 (578) & 7,341,516 (220) & - & - \tabularnewline $n=17$ & 8,089 (9) & 3,400,272 (145) & 50,175,126 (728) & 870,912 (16) & - & - \tabularnewline $n=18$ & 24,441 (10) & 16,126,398 (210) & 92,757,960 (679) & - & - & - \tabularnewline \hline \hline \pagebreak $\mathbi{r=4}$ & & & & & & \tabularnewline $n=12$ & 159 (6) & 8,532 (20) & 193,104 (121) & 44,604 (37) & - & - \tabularnewline $n=15$ & 367 (11) & 37,044 (52) & 3,053,160 (682) & 81,668,484 (8,294) & & \tabularnewline $n=16$ & 991 (11) & 271,236 (92) & 56,926,656 (2,351) & 390,829,212 (13,122) & 419,904 (12) & - \tabularnewline $n=17$ & 2,239 (11) & 1,350,612 (112) & 487,124,064 (4,539) & 1,036,246,284 (12,578) & - & - \tabularnewline \hline \hline $\mathbi{r=5}$ & & & & & & \tabularnewline $n=15$ & 751 (8) & 154,440 (44) & 17,669,304 (783) & 27,020,304 (996) & - & - \tabularnewline \hline \end{longtable} \end{landscape} \begin{thebibliography}{99} \bibitem{AschSeg} Aschbacher, M.; Segev, Y., \emph{The uniqueness of groups of Lyons type.} J.~Amer.~Math.~Soc. 5 (1992), no. 1, 75--98. \bibitem{BaBuPeRo1} Bates, C.; Bundy, D.; Perkins, S.; Rowley, P. \emph{Commuting involution graphs for symmetric groups.} J.~Algebra 266 (2003), no. 1, 133--153. \bibitem{BaBuPeRo2} Bates, C.; Bundy, D.; Perkins, S.; Rowley, P. \emph{Commuting involution graphs for finite Coxeter groups.} J.~Group Theory 6 (2003), no. 4, 461--476. \bibitem{BaBuPeRo3} Bates, C.; Bundy, D.; Perkins, S.; Rowley, P. \emph{Commuting involution graphs in special linear groups.} Comm.~Algebra 32 (2004), no. 11, 4179--4196. \bibitem{BaBuPeRo4} Bates, C.; Bundy, D.; Hart, S.; Rowley, P. \emph{Commuting involution graphs for sporadic simple groups.} J.~Algebra 316 (2007), no. 2, 849--868. \bibitem{BaBuPeRo5} Bates, C.; Bundy, D.; Hart, S.; Rowley, P. \emph{A Note on Commuting Graphs for Symmetric Groups}, Electron.~J.~Combin. 16(1) (2009), \#R6. \bibitem{BaumStein} Baumeister, B.; Stein, A. \emph{Commuting graphs of odd prime order elements in simple groups.} \arxiv{0908.2583} \bibitem{BrauerFowler} Brauer, R.; Fowler, K. A., \emph{On groups of even order.} Ann.~Math. (2) 62 (1955), 565--583. \bibitem{Bundy} Bundy, D. \emph{The connectivity of commuting graphs.} J.~Combin.~Theory Ser.~A 113 (2006), no. 6, 995--1007. \bibitem{magma} Cannon, J.J; Playoust, C. {\em An Introduction to Algebraic Programming with \textsc{Magma}}, Springer-Verlag (1997). \bibitem{Everett} Everett, A., \emph{Commuting involution graphs for 3-dimensional unitary groups.} Electron.~J.~Combin. 18(1) (2011),\#P103, \bibitem{EverettRowley} Everett, A.; Rowley, P., \emph{Commuting Involution Graphs for $4$-Dimensional Projective Symplectic Groups.} Preprint, 2010. Available from \url{http://eprints.ma.man.ac.uk/1564/} \bibitem{Fischer} Fischer, B., \emph{Finite groups generated by $3$-transpositions.} I. Invent.~Math. 13 (1971), 232--246. \bibitem{Segev1} Segev, Y., \emph{On finite homomorphic images of the multiplicative group of a division algebra.} Ann.~Math. (2) 149 (1999), no. 1, 219--251. \bibitem{Segev2} Segev, Y., \emph{The commuting graph of minimal nonsolvable groups.} Geom.~Dedicata 88 (2001), no. 1-3, 55--66. \bibitem{Segev3} Segev, Y.; Seitz, G.M. \emph{Anisotropic groups of type $A\sb n$ and the commuting graph of finite simple groups.} Pacific J.~Math. 202 (2002), no. 1, 125--225. \end{thebibliography} \end{document}