7
$\begingroup$

Suppose $S_6$ is the symmetric group on six letters and let $X$ denote the conjugacy class containing $(12)(34)$. Define a graph $\Gamma$ with vertex set $X$ and edges precisely the 2-element subsets of $X$ which commute as elements of $S_6$. I would like to know the automorphism group of the graph $\Gamma$.

P.S. These graphs are known in scientific texts as 'commuting graphs'.

$\endgroup$
2
  • $\begingroup$ An article worth pointing out in this context, despite the incorrect grammar in the article's title, seems to be Mahsa Mirzargar, Peter P. Pach, and A. R. Ashrafi: The automorphism group of commuting graph of a finite group. Bull. Korean Math. Soc. 51 (2014), No. 4, pp. 1145–1153. This article, however, seems not to contain a direct answer to OP: all results in loc. cit. are about commuting graphs on a group in its entirety, not on a conjugacy class, as in the OP. In particular, YCor's answer presently is the only answer known to me. $\endgroup$ Sep 10, 2017 at 10:21
  • $\begingroup$ You meant to ask for the isomorphism type of $U(\mathrm{Aut}(\Gamma))$, described in usual group theoretic discourse. In particular, by the formula for the cardinality of finite conjugacy classes, $\mathfrak{C}$ has cardinality $\frac{6!}{2^2\cdot 2! \ \cdot \ 1^2\cdot 2!} = 45$, so the $U(\mathrm{Aut}(\Gamma)$ described above is a subgroup of $\mathrm{Sym}(\text{$45$-element finite set})$, in other words, is a permutation group on 45 letters. In other words, your graph has 45 vertices. You probably essentially know this. I was just trying to correct my muddled comments of yesterday. $\endgroup$ Sep 11, 2017 at 12:56

2 Answers 2

9
$\begingroup$

It's an exercise to check it coincides with $\mathrm{Aut}(S_6)$ which has $S_6$ as subgroup of index 2.

Here are the steps. First, for arbitrary $n\ge 6$, consider the graph of transpositions. So this is the set $X_n$ of the $n(n-1)/2$ unordered pairs, with an edge between two whenever they are disjoint.

On $X_n$, consider the set $Y_n$ all unordered pairs of non-joined vertices (hence of the form $\{\{a,b\},\{a,c\}$ for $a,b,c$ pairwise distinct. There's a canonical map $\phi:Y_n\to\{1,\dots,n\}$ given by $\phi(\{\{a,b\},\{a,c\})=a$; we wish to show it's equivariant for the group action.

Link two elements of $Y_n$ if they are disjoint and contained no pair of joined vertices. Then any two linked elements of $Y_n$ have the same image by $\phi$ (check! this uses the disjointness assumption). Next consider the equivalence relation on $Y_n$ generated by this equivalence relation. The only 2-element subsets in $Y_n$ with same image by $\phi$ but not linked have the form, up to permutation, $\{\{12,13\},\{12,14\}\}$. But one indeed have $\{12,13\}-\{15,16\}-\{12,14\}$. So for $n\ge 6$, the equivalence relation on $Y_n$ generated by being linked consists of being in the same fibers of $\phi$, and hence the automorphism group of $X_n$ acts on $\{1,\dots,n\}$. This action is easily seen to be faithful. Since the permutation group $S_n$ already acts, this shows that the automorphism group of $X_n$ is $S_n$.

Next in $S_n$ for $n\ge 7$, the transpositions are the only elements whose centralizer has order $2(n-2)!$, i.e., form the only conjugacy class of order $n(n-1)/2$, and hence $\mathrm{Aut}(\mathrm{Comm}(S_n))$ stabilizes its subgraph $X_n$. Again a little argument shows that this action is faithful (i.e. an automorphism of $\mathrm{Comm}(S_n)$ fixing pointwise the transpositions is the identity; also for $n=6$.

For $n=6$ on the other hand, there are 2 conjugacy classes of order 15: transpositions and triple transpositions. They are switched by non-inner automorphisms. Hence the previous argument applies to the subgroup of index 2 of $\mathrm{Aut}(\mathrm{Comm}(S_6))$ stabilizing $S_6$ and the result follows.


Update: my answer above was incomplete since it does not address double transpositions; let me now answer the question fully; this will actually make use of the above answer about the graph of transpositions!

Let us consider the graph $Z_n$ of double transpositions. Let me stick to $n=6$. I'll denote the permutation $(ab)(cd)$ as $(ab|cd)$ to avoid too many parentheses/commas.

In $Z_6$, there are triangles defined as follows:

  1. Triangles of type I: $S_6$-permutes of the triangle $T_1=\{(12|34),(13|24),(14|23)\}$.
  2. Triangles of type II: $S_6$-permutes of the triangles $T_2=\{(12|34),(12|56),(34|56)\}$.

It is straightforward that every triangle is of type I or type II, that the $S_6$-action preserves types of triangles, and that elements of $\mathrm{Aut}(S_6)\smallsetminus S_6$ exchange the two types. Consider the graph $W_6$ whose vertices are triangles in $Z_6$ and such that there is an edge between two triangles whenever they have a common vertex. For instance, there is an edge between $T_1$ and $T_2$ since they have the common vertex $(12|34)$. It is easy to check that $W_6$ is connected. Vertices of $W_6$ thus have type I or II, and we see that no vertices of the same type are joined. So $W_6$ is bipartite. Thus, for vertices of $W_6$, the relation "to have the same type" (which is not defined intrinsically) is indeed intrinsic, as it is equivalent to be at even distance. In particular, the isometry group $G$ of $W_6$ preserves the partition by types. Let $G'$ be its index 2 subgroup of type-preserving isometries. Define $W'_6$ as the graph consisting of vertices of type I in $W_6$, linked whenever they have distance at most 2 in $W_6$. We see that $W'_6$ is canonically isomorphic to the transposition graph! The isomorphism is given by mapping the triangle $T_1=\{(12|34),(13|24),(14|23)\}$ to $(56)$, etc.

By the previous result on $X_6$, we deduce that $G'=S_6$. It follows that $G$ is reduced to $\mathrm{Aut}(S_6)$ (since clearly an isometry of $W_6$ that is identity on vertices of type I has to be the identity). To conclude that $\mathrm{Aut}(Z_6)$ is reduced to $\mathrm{Aut}(S_6)$, it is enough to show that the canonical homomorphism $\mathrm{Aut}(Z_6)\to\mathrm{Aut}(W_6)$ is injective. This is also immediate: for $f$ in the kernel, any double transposition belongs to exactly two triangles, i.e., two unordered triples of linked vertices, each of which is $f$-invariant, and hence is fixed by $f$. So we have proved that $\mathrm{Aut}(Z_6)$ is reduced to $\mathrm{Aut}(S_6)$, answering the original question.

$\endgroup$
0
6
$\begingroup$

Easy enough

sage: G=SymmetricGroup(6)
sage: cc=G.conjugacy_class([2,2,1,1])
sage: gr=Graph([cc, lambda a,b: a*b==b*a and a!=b])
sage: gr.automorphism_group().cardinality()
1440
$\endgroup$
11
  • $\begingroup$ For inexperience users: "conjugacy_class(...)" makes Sage create the set of permutations in G which are conjugate to, e.g., the representative $(12)(34)$. Hopefully needless to say, this does not depend on the representative, only on the ordered partition of $6$, which is why the argument $[2,2,1,1]$, which corresponds to $2+2+1+1$, is used here. Moreover, the OP asked for the structure of this automorphism group, not only its order. I take the GP wiki's word for it that there are a whopping 5958 isomorphism types of them. $\endgroup$ Sep 10, 2017 at 9:44
  • 6
    $\begingroup$ So while this is certainly a nice and useful answer, one should remain aware of the following: (0) Sage's utterances are not mathematical proofs, (1) YCor's answer seems to be a correct mathematical proof and accomplishes quite a bit more than Sage here: YCor seems to have found the correct isomorphism type in the haystack of 5958 disctinct isomorphism types, (2) the initial 'Easy enough' is slightly grating (to me). I can understand how this happens (not being a native speaker), yet it seems to make this look easier than it actually is. $\endgroup$ Sep 10, 2017 at 9:48
  • 4
    $\begingroup$ In this case knowing the order is enough - we know the outer automorphism group of $S_6$ acts on the graph, the only question is whether there is more. Second, I think anyone who wants to find the automorphism group of such a graph should automatically turn to a computer, and I suspect this may be part of F.C.'s motivation for the title of their answer. $\endgroup$ Sep 10, 2017 at 12:33
  • 1
    $\begingroup$ @PeterHeinig: In fact, $\operatorname{Aut}(S_6)$ acts on the graph, because the double transpositions are invariant under the automorphism group. To see this, note that the alternating group is invariant under $\operatorname{Aut}(S_6)$, as $A_6$ is the only normal subgroup of index $2$ in $S_6$, and the only elements of order $2$ in $A_6$ are just the double transpositions. $\endgroup$ Sep 10, 2017 at 16:14
  • 1
    $\begingroup$ Another proof that $X$ is $\operatorname{Aut}(S_6)$-invariant: The elements in $X$ have centralizer of order $16$, the other involutions centralizer of order $48$. $\endgroup$ Sep 10, 2017 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.