Automorphism group of the complete transposition graph

Abstract

The complete transposition graph is defined to be the graph whose vertices are the elements of the symmetric group $S_n$, and two vertices $\alpha$ and $\beta$ are adjacent in this graph iff there is some transposition (i, j) such that $\alpha =(i,j) \beta$. Thus, the complete transposition graph is the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ of the symmetric group generated by the set S of all transpositions. An open problem in the literature is to determine which Cayley graphs are normal. It was shown recently that the Cayley graph generated by four cyclically adjacent transpositions is non-normal. In the present paper, it is proved that the complete transposition graph is not a normal Cayley graph, for all $n \ge 3$. Furthermore, the automorphism group of the complete transposition graph is shown to equal

$$\begin{aligned} \mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S)) = (R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)) \rtimes \mathbb {Z}_2, \end{aligned}$$

where $R(S_n)$ is the right regular representation of $S_n$, $\mathop {\mathrm {Inn}}\nolimits (S_n)$ is the group of inner automorphisms of $S_n$, and $\mathbb {Z}_2 = \langle h \rangle$, where h is the map $\alpha \mapsto \alpha ^{-1}$.

1 Introduction

Let $X=(V,E)$ be a simple, undirected graph. An automorphism of X is a permutation of its vertex set that preserves adjacency (cf. Tutte [10], Biggs [1]). The set $\{g \in \mathop {\mathrm {Sym}}\nolimits (V): E^g=E\}$ of all automorphisms of X is called the automorphism group of X and is denoted by $\mathop {\mathrm {Aut}}\nolimits (X)$. Given a group H and a subset $S \subseteq H$ such that $1 \notin S$ and $S=S^{-1}$, the Cayley graph of H with respect to the S, denoted by $\mathop {\mathrm {Cay}}\nolimits (H,S)$, is defined to be the graph with vertex set H and edge set $\{(h,sh): h \in H, s \in S\}$. The right regular representation R(H) acts as a group of automorphisms of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (H,S)$, and hence, a Cayley graph is always vertex-transitive. The set of automorphisms of the group H that fixes S setwise, denoted by $\mathop {\mathrm {Aut}}\nolimits (H,S)$, is a subgroup of the stabilizer $\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (H,S))_e$ of the vertex e (cf. [1]). A Cayley graph $\mathop {\mathrm {Cay}}\nolimits (H,S)$ is said to be normal if R(H) is a normal subgroup of $\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (H,S))$, or equivalently, if $\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (H,S)) = R(H) \rtimes \mathop {\mathrm {Aut}}\nolimits (H,S)$ (cf. [6, 12]).

An open problem in the literature is to determine which Cayley graphs are normal. Let S be a set of transpositions generating $S_n$. The transposition graph of S is defined to be the graph with vertex set $\{1,\ldots ,n\}$ and with two vertices i and j being adjacent in this graph iff $(i,j) \in S$. A set of transpositions S generates $S_n$ iff the transposition of S is connected. Godsil and Royle [7] showed that if the transposition graph of S is an asymmetric tree, then the automorphism group of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is isomorphic to $S_n$. Feng [4] showed that if the transposition graph of S is an arbitrary tree, then the automorphism group of $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is $R(S_n) \rtimes \mathop {\mathrm {Aut}}\nolimits (S_n,S)$. Ganesan [5] showed that if the girth of the transposition graph of S is at least 5, then the automorphism group of $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is $R(S_n) \rtimes \mathop {\mathrm {Aut}}\nolimits (S_n,S)$. In all these cases, the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal. Ganesan [5] showed that if the transposition graph of S is a 4-cycle graph, then $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is non-normal.

While one can often obtain some automorphisms of a graph, it is often difficult to prove that one has obtained the (full) automorphism group. In the present paper, we obtain the full automorphism group of the complete transposition graph. The complete transposition graph has also been studied for consideration as the topology of interconnection networks [8]. Many authors have investigated the automorphism group of other graphs that arise as topologies of interconnection networks; for example, see [2, 3, 13, 14].

Notation Throughout this paper, S represents a set of transpositions generating $S_n$, $X:=\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ and $G:=\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))$. $X_r(e)$ denotes the set of vertices in X whose distance to the identity vertex e is exactly r. Thus, $X_0(e) = \{e\}$ and $X_1(e)=S$. Greek letters $\alpha , \beta ,\ldots \in S_n$ usually represent the vertices of X, and lowercase Latin letters $g, h,\ldots \in \mathop {\mathrm {Sym}}\nolimits (S_n)$ often represent automorphisms of X. The support of a permutation $\alpha$ is the set of points moved by $\alpha$. For a graph X, $L_e:=L_e(X)$ denotes the set of automorphisms of X that fixes the vertex e and each of its neighbors in X.

The main result of this paper is the following:

Theorem 1.1

Let S be the set of all transpositions in $S_n$ ($n \ge 3$). Then, the automorphism group of the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is

$$\begin{aligned} \mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S)) = (R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)) \rtimes \mathbb {Z}_2, \end{aligned}$$

where $R(S_n)$ is the right regular representation of $S_n$, $\mathop {\mathrm {Inn}}\nolimits (S_n)$ is the inner automorphism group of $S_n$, and $\mathbb {Z}_2 = \langle h \rangle$, where h is the map $\alpha \mapsto \alpha ^{-1}$. The complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is non-normal.

2 Preliminaries

Whitney [11] investigated whether a graph T is uniquely determined by its line graph L(T) and showed that the answer is in the affirmative for all connected graphs T on five or more vertices (this is because the only exceptions occur when T is $K_3$ or $K_{1,3}$, which have fewer than five vertices). More specifically, two connected graphs on five or more vertices are isomorphic iff their line graphs are isomorphic. And if T is a connected graph that has five or more vertices, then every automorphism of the line graph L(T) is induced by a unique automorphism of T, and the automorphism groups of T and of L(T) are isomorphic:

Theorem 2.1

(Whitney [11]) Let T be a connected graph containing at least five vertices. Then, the automorphism group of T and of its line graph L(T) are isomorphic.

Theorem 2.2

(Feng [4]) Let S be a set of transpositions in $S_n$, and let $T=T(S)$ denote the transposition graph of S. Then, $\mathop {\mathrm {Aut}}\nolimits (S_n,S) \cong \mathop {\mathrm {Aut}}\nolimits (T)$.

Feng’s result (Theorem 2.2) does not require that S generate $S_n$, i.e., it holds even if the transposition graph of S is not connected.

Theorem 2.3

(Suzuki [9, Chapter 3, Section 2] If $n \ge 2$ and $n \ne 6$, then $\mathop {\mathrm {Aut}}\nolimits (S_n)=\mathop {\mathrm {Inn}}\nolimits (S_n)$. If $n=6$, then $|\mathop {\mathrm {Aut}}\nolimits (S_n):\mathop {\mathrm {Inn}}\nolimits (S_n)|=2$, and every element in $\mathop {\mathrm {Aut}}\nolimits (S_n) - \mathop {\mathrm {Inn}}\nolimits (S_n)$ maps a transposition to a product of three disjoint transpositions.

3 An equivalent condition for normality

Let S be a set of transpositions generating $S_n$ ($n \ge 5$). Let $X:=\mathop {\mathrm {Cay}}\nolimits (S_n,S)$, and let $L_e=L_e(X)$ denote the set of automorphisms of X that fixes the identity vertex e and each of its neighbors. In this section, an equivalent condition for normality of $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is obtained: The Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal iff $L_e=1$. It is not assumed in this section that S is the complete set of transpositions in $S_n$.

Lemma 3.1

Let S be a set of transpositions generating $S_n$. Let $\tau , \kappa \in S, \tau \ne \kappa$. Then, $\tau \kappa = \kappa \tau$ if and only if there is a unique 4-cycle in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e,\tau$ and $\kappa$.

Proof

Suppose $\tau \kappa =\kappa \tau$. Then, $\tau$ and $\kappa$ have disjoint support. Let $\omega$ be a common neighbor of the vertices $\tau$ and $\kappa$ in the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$. By definition of the adjacency relation in the Cayley graph, there exist $x,y\in S$ such that $x\tau =y\kappa =\omega$. Observe that $x\tau =y\kappa$ iff $\tau \kappa =xy$. But since $\kappa$ and $\tau$ have disjoint support, $\tau \kappa =xy$ iff $\tau =x$ and $\kappa =y$ or $\tau =y$ and $\kappa =x$. Thus, $\omega$ is either the vertex e or the vertex $\tau \kappa$. Hence, there exists a unique 4-cycle in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e,\tau$ and $\kappa$, namely the cycle $(e,\tau ,\tau \kappa =\kappa \tau ,\kappa ,e)$.

To prove the converse, suppose $\tau \kappa \ne \kappa \tau$. Then, $\tau$ and $\kappa$ have overlapping support; without loss of generality, take $\tau =(1,2)$ and $\kappa =(2,3)$. We consider two cases, depending on whether $(1,3) \in S$. First, suppose $(1,3) \notin S$. Let $\omega$ be a common neighbor of $\tau$ and $\kappa$. So, $\omega =x\tau =y\kappa$ for some $x,y \in S$. As before, $x\tau =y\kappa$ iff $xy=\tau \kappa =(1,2)(2,3)=(1,3,2)$. The only ways to decompose (1, 3, 2) as a product of two transpositions are as $(1,3,2)=(1,2)(2,3)=(3,2)(1,3)=(1,3)(1,2)$. Since $(1,3) \notin S$, we must have $x=(1,2)$ and $y=(2,3)$, whence $\omega =e$. Thus, $\tau$ and $\kappa$ have only one common neighbor, namely e. Therefore, there does not exist any 4-cycle in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e,\tau$ and $\kappa$.

Now suppose $\rho :=(1,3) \in S$. Then, S contains the three transpositions $\tau =(1,2),\kappa =(2,3)$ and $\rho =(1,3)$. The Cayley graph of the permutation group generated by these transpositions is the complete bipartite graph $K_{3,3}$. Hence, $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ contains as a subgraph the complete bipartite graph $K_{3,3}$ with bipartition $\{e,\kappa \tau ,\tau \kappa \}$ and $\{\tau ,\kappa ,\rho \}$. There are exactly two 4-cycles in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e,\tau$ and $\kappa$, namely the 4-cycle through the vertex $\kappa \tau$ and the 4-cycle through the vertex $\kappa \tau$. Thus, while there exists a 4-cycle in this case, it is not unique. $\square$

Proposition 3.2

Let S be a set of transpositions generating $S_n$, and let $G:=\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))$. If $g \in G_e$, then g restricted to S is an automorphism of the line graph of the transposition graph of S.

Proof

Let $\tau , \kappa \in S$ and $g \in G_e$. Let L(T) denote the line graph of the transposition graph of S. Two transpositions commute iff they have disjoint support. It needs to be shown that the restriction of g to S is an automorphism of L(T), i.e., that $\tau ,\kappa$ have disjoint support iff $\tau ^g,\kappa ^g$ have disjoint support. Thus, it suffices to show that $\tau \kappa =\kappa \tau$ iff $\tau ^g \kappa ^g=\kappa ^g \tau ^g$. By Lemma 3.1, $\tau \kappa =\kappa \tau$ iff there is a unique 4-cycle in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e, \tau$ and $\kappa$, which is the case iff there is a unique 4-cycle in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ containing $e, \tau ^g$ and $\kappa ^g$, which is the case iff $\tau ^g \kappa ^g = \kappa ^g \tau ^g$. $\square$

Theorem 3.3

Let S be a set of transpositions generating $S_n$ ($n \ge 5$). Let $L_e$ denote the set of automorphisms of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ that fixes the vertex e and each of its neighbors. Then, $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal if and only if $L_e=1$.

Proof

For the necessity, suppose $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal. Then, $G_e = \mathop {\mathrm {Aut}}\nolimits (S_n,S)$ (cf. [12]). Since S generates $S_n$, each element of $\mathop {\mathrm {Aut}}\nolimits (S_n,S)$ is uniquely determined by its action on S. Hence, $L_e=1$. For the sufficiency, we have $L_e=1$. Hence, $G_e = G_e/L_e \le \mathop {\mathrm {Aut}}\nolimits (L(T))$. By Theorem 2.1, $\mathop {\mathrm {Aut}}\nolimits (L(T)) \cong \mathop {\mathrm {Aut}}\nolimits (T)$ and by Theorem 2.2, $\mathop {\mathrm {Aut}}\nolimits (T) \cong \mathop {\mathrm {Aut}}\nolimits (S_n,S)$. It follows that $|G_e| = |\mathop {\mathrm {Aut}}\nolimits (S_n,S)|$. Clearly, $\mathop {\mathrm {Aut}}\nolimits (S_n,S) \le G_e$. Thus, we have $G_e = \mathop {\mathrm {Aut}}\nolimits (S_n,S)$, and so, $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal. $\square$

4 Non-normality of the complete transposition graph

Theorem 4.1

Let S be the set of all transpositions in $S_n~ (n \ge 3)$. Then, the map $\alpha \mapsto \alpha ^{-1}$ is an automorphism of the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$. In particular, $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is non-normal.

Proof

Let G denote the automorphism group of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$, and let e denote the identity element in $S_n$. The Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is normal if and only if the stabilizer $G_e \subseteq \mathop {\mathrm {Aut}}\nolimits (S_n)$ (cf. Xu [12, Proposition 1.5]). Thus, to prove that $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is non-normal, it suffices to show that $G_e$ contains an element which is not a homomorphism from $S_n$ to itself. Consider the map $\alpha \mapsto \alpha ^{-1}$ from $S_n$ to itself. Since $n \ge 3$, $S_n$ is non-abelian, whence the map $\alpha \mapsto \alpha ^{-1}$ is not a homomorphism. It suffices to show that the map $\alpha \mapsto \alpha ^{-1}$ is an automorphism of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$.

Let $\alpha$ and $\beta$ be two adjacent vertices in the graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$. Then, $\alpha$ and $\beta$ differ by a transposition, i.e., there is some $i \ne j$ such that $\beta =(i,j)\alpha$. We shall prove that $\alpha ^{-1}$ and $\beta ^{-1}$ also differ by a transposition; since the set S contains all transpositions in $S_n$, it would follow that $\alpha ^{-1}$ and $\beta ^{-1}$ are also adjacent vertices in $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$.

To show that the map $h: \alpha \mapsto \alpha ^{-1}, \alpha \in S_n$ is an automorphism of the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$, it suffices to show that for any $u,v \in S_n$, if $uv^{-1}$ is a transposition, then $u^{-1}v$ is a transposition. In fact, letting $uv^{-1}=(i,j)$, we have $u^{-1}v = v^{-1} (i,j)v$ is a transposition.

We have $1 \ne h \in \mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))_e {\setminus } \mathop {\mathrm {Aut}}\nolimits (S_n,S)$, and so, $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is non-normal. $\square$

Theorem 4.2

Let S be the set of all transpositions in $S_n$ ($n \ge 3$). Then,

$$\begin{aligned} \mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S)) \supseteq (R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)) \rtimes \mathbb {Z}_2, \end{aligned}$$

where $R(S_n)$ is the right regular representation of $S_n$, $\mathop {\mathrm {Inn}}\nolimits (S_n)$ is the inner automorphism group of $S_n$, and $\mathbb {Z}_2 = \langle h \rangle$, and h is the map $\alpha \mapsto \alpha ^{-1}$.

Proof

Let $G:=\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))$ denote the automorphism group of the complete transposition graph. Since $R(S_n)$ and $\mathop {\mathrm {Aut}}\nolimits (S_n,S)$ are automorphisms of the Cayley graph (cf. [1]), we have $G \supseteq R(S_n) \rtimes \mathop {\mathrm {Aut}}\nolimits (S_n,S)$. Also, S is a non-empty set of transpositions, so by Theorem 2.3, every element in $\mathop {\mathrm {Aut}}\nolimits (S_n,S)$ is an inner automorphism of $S_n$. In fact, the elements in $\mathop {\mathrm {Aut}}\nolimits (S_n,S)$ are exactly conjugations by the automorphisms of the transposition graph of S (cf. Theorem 2.2 and [4]). The transposition graph of S is complete, and hence, $\mathop {\mathrm {Aut}}\nolimits (S_n,S) = \mathop {\mathrm {Inn}}\nolimits (S_n) \cong S_n$.

The inverse map $(h: \alpha \mapsto \alpha ^{-1})$ fixes the identity vertex e of the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ and hence fixes its neighbors S setwise. It is clear that $h \notin R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)$ for otherwise, $h \in \mathop {\mathrm {Aut}}\nolimits (S_n,S)$ which is clearly impossible. Thus, G contains $H:= (R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)) \rtimes \mathbb {Z}_2$, where $\mathbb {Z}_2 := \langle h \rangle$, and $R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)$ has index 2 in H and hence is a normal subgroup in H. $\square$

This implies that the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ has at least $2(n!)^2$ automorphisms, for all $n \ge 3$.

Let S be a set of transpositions generating $S_n$ ($n \ge 3$). The only Cayley graphs $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ known so far to be non-normal are those arising from the 4-cycle transposition graph and from the transposition graphs that are complete.

5 Automorphism group of the complete transposition graph

Let S be the set of all transpositions in $S_n$. In the previous section, a set of $2(n!)^2$ automorphisms was exhibited for the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$. In this section, it is proved that the complete transposition graph has no other automorphisms, which implies that the subgroup given in Theorem 4.2 is in fact the full automorphism group.

Theorem 5.1

Let S be the set of all transpositions in $S_n$, and let X be the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$. Let $L_e(X)$ denote the set of automorphisms of X that fixes the vertex e and each of its neighbors. Then, $L_e(X) = \{1,h \}$, where $h: V(X) \rightarrow V(X)$ is the map $\alpha \rightarrow \alpha ^{-1}$.

Proof

By Proposition 4.1, $L_e \supseteq \{1,h\}$. We need to show that $L_e$ has no other elements.

The vertex e of X corresponding to the identity element in $S_n$ has as its neighbors the set S of all transpositions in $S_n$. Suppose g is an automorphism of X that fixes the vertex e and each vertex in S; so $g \in L_e(X)$. Then, the set of common neighbors of the three vertices (1, 2), (2, 3) and (1, 3) in S, namely the set $\Delta :=\{(1,2,3),(1,3,2)\}$, is a fixed block of g. We show that the action of $L_e:=L_e(X)$ on $\Delta$ uniquely determines its action on all the remaining vertices, i.e., that if $g \in L_e$ fixes $\Delta$ pointwise, then $g=1$, and if g interchanges (1, 2, 3) and (1, 3, 2), then g extends uniquely to the automorphism $\alpha \mapsto \alpha ^{-1}$ of X.

Suppose $g \in L_e$ and g fixes $\Delta = \{\alpha ,\alpha ^{-1} \}$ pointwise, where $\alpha =(1,2,3)$. Let $\beta =(2,3,4)$. We show g fixes $\{\beta ,\beta ^{-1} \}$ also pointwise. Given any vertex $\gamma \in V(X)$ that is a 3-cycle permutation (so, the distance in X between $\gamma$ and e is 2), let $W_\gamma$ be the set of neighbors of $\gamma$ that have distance 3 to e in X (see Fig. 1).

Fig. 1

Distance partition of the Cayley graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$

We claim that $|W_\alpha \cap W_\beta |=|W_{\alpha ^{-1}} \cap W_{\beta ^{-1}}|=2$ and $|W_\alpha \cap W_{\beta ^{-1}} | = |W_{\alpha ^{-1}} \cap W_\beta |=1$. Suppose some neighbor of $\alpha =(1,2,3)$ is also a neighbor of $\beta =(2,3,4)$. Then, $\exists x, y \in S$ such that $x \alpha = y \beta$. Hence, $\alpha \beta ^{-1} = (1,2,3)(2,3,4)=(1,4,3)=x^{-1}y=xy$. Now $(1,4,3)=(1,4)(1,3)=(1,3)(3,4)=(3,4)(1,4)$. So, $x \in \{(1,4),(1,3),(3,4)\}$. But if $x=(1,3)$, then $x \alpha = (1,3)(1,2,3)=(2,3)$, so $x \alpha$ has distance 1 to e, and $x \alpha \notin W_\alpha$. Thus, there are two solutions (1, 4) and (3, 4) for x in $x \alpha =y \beta \in W_\alpha \cap W_\beta$. Hence, $|W_\alpha \cap W_\beta |=2$. Similarly, $|W_{\alpha ^{-1}} \cap W_{\beta ^{-1}}|=2$. Now consider $|W_\alpha \cap W_{\beta ^{-1}} |$. If $x,y \in S$ are such that $x \alpha =y \beta ^{-1}$, then $\alpha \beta =(1,2,3)(2,3,4)=(1,3)(2,4)=xy$. But if $x=(1,3)$, then $y \alpha =(1,3)(1,2,3)=(2,3) \notin W_\alpha$. Thus, $x=(2,4)$, $y=(1,3)$, $x \alpha = (2,4)(1,2,3)=(1,2,4,3)$ and $|W_\alpha \cap W_{\beta ^{-1}} | = |\{(1,2,4,3)\}|=1$.

Since g is an automorphism of X, it preserves the number of common neighbors of any two vertices. Thus, if g fixes $\alpha$ and $\alpha ^{-1}$, by the result in the previous paragraph, g also fixes $\beta$ and $\beta ^{-1}$. More generally, if g fixes vertex (j, k, i), then g also fixes $(j,k,\ell )$ for each $\ell \ne j,k,i$. Repeating this process, we see that g fixes all vertices that are 3-cycles in $S_n$. The only other vertices having distance 2 to e in X are those permutations that are a product of two disjoint transpositions, and each of these vertices is also fixed by g by Lemma 3.1.

Thus, if $g \in L_e(X)$ fixes vertex (1, 2, 3), then g fixes each vertex that has distance 2 to e. Let $X_r(e)$ denote the set of vertices that have distance r to e. We have that g fixes $X_0(e)$ and $X_1(e)$ pointwise since $g \in L_e$, and it was just shown that if g fixes $(1,2,3) \in X_2(e)$, then g also fixes $X_2(e)$ pointwise. Since g is an automorphism, it maps the neighbors of a vertex $\alpha$ to the neighbors of $\alpha ^g$. But by the next proposition (Proposition 5.2), any two distinct vertices in $X_k(e)$ $(k \ge 3)$ have a different set of neighbors in $X_{k-1}(e)$. Thus, if g fixes $X_{k-1}(e)$ pointwise, then g also fixes $X_k(e)$ pointwise. By induction on k, g is the trivial automorphism.

If $g \in L_e$ interchanges (1, 2, 3) and (1, 3, 2), and h is the map $\alpha \mapsto \alpha ^{-1}$, then $gh=1$ by the previous paragraph, whence $g=h^{-1}=h$. Thus, $L_e = \{1,h\} \cong C_2$. $\square$

In the proof above, we used the following result:

Proposition 5.2

Let $n \ge 5$ and let $X=\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ be the complete transposition graph. Let $\alpha$ and $\beta$ be distinct vertices in $X_k(e)$ $(k \ge 3)$. Then, the sets of neighbors of $\alpha$ in $X_{k-1}(e)$ and of $\beta$ in $X_{k-1}(e)$ are not equal.

Proof

Each permutation in $X_k(e)$ can be written as a product of k transpositions, and since the length of this product is minimal, the edges of the transposition graph of S corresponding to these k transpositions form a forest.

Let $\alpha , \beta \in X_k(e)$. If the support of $\alpha$ and of $\beta$ are not equal, then they clearly have different sets of neighbors in $X_{k-1}(e)$ because some transposition in a forest that yielded $\alpha$ is incident to a vertex that does not belong to any forest that yields $\beta$. (For example, if $\alpha =(1,2,3)(4,5)$ and $\beta =(1,2,3,4)$ are two vertices in $X_3(e)$, then $\alpha$ does have a neighbor (1, 2)(4, 5) in $X_2(e)$ whose support contains 5, but $\beta$ does not have such a neighbor.)

Now suppose $\alpha$ and $\beta$ are distinct vertices in $X_k(e)$ that have the same support. Since $\alpha \ne \beta$, there is a point in their common support, 1 say, such that $1^\alpha \ne 1^\beta$. So, suppose $\alpha =(1,2,x_1,\ldots ,x_r) \alpha '$ and $\beta =(1,3,y_1,\ldots ,y_t) \beta '$. We consider three cases:

Case 1 Suppose $\alpha ' = \beta '=1$. Then, $\alpha$ and $\beta$ are cyclic permutations of the same length r, where $r \ge 4$ since $k \ge 3$. If $\alpha =\beta ^{-1}$, then we can find two consecutive points in the cycle of $\alpha$ that are not consecutive in the cycle of $\beta$. Suppose i, j are these two points; so $\alpha =(i,j,k,\ldots ,m)$ and $\beta =(i,\ell ,\ldots ,j,p,\ldots )$. Then, $\gamma =(i,j)(k,\ldots ,m)$ is a neighbor of $\alpha$ in $X_{k-1}(e)$ but not of $\beta$. For if $s \gamma =\beta$ for some transposition s, then $s=\beta \gamma ^{-1} = (i,\ell ,\ldots ,j,p,\ldots )(i,j)(k,m,\ldots )$. Now s moves i since $i^s = i^{\beta \gamma ^{-1}}=\ell ^{\gamma ^{-1}} \ne i$. Also, s moves j since $j^s=p^{\gamma ^{-1}} \ne j$. If $s=(i,j)$, then $(i,j) = (i,\ell ,\ldots ,j,p,\ldots )(k,m,\ldots )(i,j)$, whence $(i,\ell ,\ldots ,j,p,\ldots ,q)(k,m,\ldots )=1$, which is a contradiction since q is not fixed by the left-hand side but is fixed by the right-hand side. Thus, s moves at least 3 points. But then s is not a transposition, a contradiction. Hence, $\beta$ does not have $\gamma$ as a neighbor.

If $\alpha =\beta ^{-1} = (\alpha _1,\ldots ,\alpha _r)$, then $(\alpha _1,\ldots ,\alpha _{r-1})$ is a neighbor of $\alpha$ in $X_{k-1}(e)$ but not of $\beta$.

Case 2 Suppose $\alpha '=\beta ' \ne 1$. So, $\alpha =(1,2,x_1,\ldots ,x_r) (\alpha _1,\ldots ,\alpha _s) \alpha ''$, $\beta =(1,3,y_1,\ldots ,y_t)(\alpha _1,\ldots ,\alpha _s) \alpha ''$ for some $s \ge 2$ and some (possibly trivial) permutation $\alpha ''$. Let $\gamma =(1,2,x_1,\ldots ,x_r)(\alpha _1,\ldots ,\alpha _{s-1}) \alpha ''$. Then, $\gamma$ is a neighbor of $\alpha$ but not of $\beta$.

Case 3 Suppose $\alpha ' \ne \beta '$. So, $\alpha =(1,2,x_1,\ldots ,x_r) \alpha '$ and $\beta = (1,3,y_1,\ldots ,y_t) \beta '$ are in $X_k(e)$. If the supports of $\alpha '$ and of $\beta '$ are equal, then take $\gamma :=(1,2,x_1,\ldots ,x_r) \gamma '$, where $\gamma '$ is any vertex that is adjacent in X to $\alpha '$ and that lies on a shortest $e-\alpha '$ path in X. Then, $\gamma$ is adjacent to $\alpha$ but not to $\beta$.

On the other hand, if the supports of $\alpha '$ and of $\beta '$ are not equal, we consider three subcases:

• (i) Suppose $r=t=0$. Then, $\alpha =(1,2)\alpha ',\beta =(1,3)\beta '$. Take $\gamma =(1,2)\gamma '$ where $\gamma '$ is any vertex in X adjacent to $\alpha '$ and such that $\gamma$ lies on a shortest $e-\alpha '$ path in X. Then, $\gamma$ is a neighbor of $\alpha$ but not of $\beta$ because if s is a transposition, then $s \gamma = s (1,2) \gamma '$ will either split a cycle in $\gamma$ or merge two cycles in $\gamma$, neither of which can produce $(1,3)\beta '$.

• (ii) Suppose $r \ge 1$ and $t=0$. Then, $\beta =(1,3)\beta '$. Take $\gamma$ to be $(1,2)(x_1,\ldots ,x_r) \alpha '$. As in subcase (i), there does not exist any transposition s such that $s \gamma = \beta$.

• (iii) Suppose $r,t \ge 1$. Let $\alpha = (1,2,x_1,\ldots ,x_r) \alpha ' = \alpha ^0 \alpha '$ and $\beta = (1,3,y_1,\ldots ,y_t) \beta ' = \beta ^0 \beta '$. Let $\mathop {\mathrm {supp}}\nolimits (\alpha )$ denote the support of the permutation $\alpha$.

If $3 \notin \mathop {\mathrm {supp}}\nolimits (\alpha ^0)$, take $\gamma = (1,3)(y_1,\ldots ,y_t) \beta '$. Then, $\gamma$ is a neighbor of $\beta$. But if $\alpha =s \gamma$ for some transposition s, then s must modify the cycle (1, 3) of $\gamma$ and hence must merge this cycle with another one. The merged cycle will contain both 1 and 3, whence $s \gamma \ne \alpha$ because $3 \notin \mathop {\mathrm {supp}}\nolimits (\alpha ^0)$. Similarly, if $2 \notin \mathop {\mathrm {supp}}\nolimits (\beta ^0)$, then take $\gamma =(1,2)(x_1,\ldots ,x_r) \alpha '$, and $\gamma$ is a neighbor of $\alpha$ but not of $\beta$.

Finally, suppose $3 \in \mathop {\mathrm {supp}}\nolimits (\alpha ^0)$ and $2 \in \mathop {\mathrm {supp}}\nolimits (\beta ^0)$. Split $\alpha ^0=(1,2,\ldots ,3,\ldots )$ before the 3 to get $\gamma ^0=(1,2,\ldots )(3,\ldots )$. Let $\gamma :=\gamma ^0 \alpha '$. Then, $\gamma$ is a neighbor of $\alpha$. If $\gamma$ is also a neighbor of $\beta =(1,3,y_1,\ldots ,y_t) \beta '$, then $s \gamma =\beta$ for some s that merges the two cycles in $\gamma ^0$. But such a merge will produce a single cycle that has the same support as $\alpha ^0$, whereas $\mathop {\mathrm {supp}}\nolimits (\alpha ^0) \ne \mathop {\mathrm {supp}}\nolimits (\beta ^0)$ by hypothesis. Hence, $\gamma$ is not a neighbor of $\beta$. $\square$

Corollary 5.3

Let S be the set of all transpositions in $S_n$ ($n \ge 3$). Then,

$$\begin{aligned} |\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))| \le 2(n!)^2. \end{aligned}$$

Proof

Let $G:=\mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S))$. The upper bound is verified to be exact if $n=3,4$ by computer simulations. If $n \ge 5$, by Lemma 3.2, every element in $G_e$, when restricted to S, is an automorphism of the line graph of the transposition graph of S. The transposition graph is complete, and hence, its line graph has automorphism group isomorphic to $S_n$ (cf. Theorem 2.1). Hence, $|G_e| \le |S_n|~ |L_e|$. Also, $|L_e|=2$, hence $|G_e| \le 2(n!)$. Thus, $|G| = |V(X)|~ |G_e| \le n! (2n!)$. $\square$

By Corollary 5.3, the subgroup given in Theorem 4.2 is in fact the full automorphism group:

Corollary 5.4

Let S be the set of all transpositions in $S_n$ ($n \ge 3$). Then, the automorphism group of the complete transposition graph $\mathop {\mathrm {Cay}}\nolimits (S_n,S)$ is

$$\begin{aligned} \mathop {\mathrm {Aut}}\nolimits (\mathop {\mathrm {Cay}}\nolimits (S_n,S)) = (R(S_n) \rtimes \mathop {\mathrm {Inn}}\nolimits (S_n)) \rtimes \mathbb {Z}_2, \end{aligned}$$

where $R(S_n)$ is the right regular representation of $S_n$, $\mathop {\mathrm {Inn}}\nolimits (S_n)$ is the inner automorphism group of $S_n$, and $\mathbb {Z}_2 = \langle h \rangle$, where h is the map $\alpha \mapsto \alpha ^{-1}$.