Commuting graph

New term: back to some mathematics, at last!

I have been puzzling in a low-key way on a problem on commuting graphs of finite groups, without success, since supervising a Masters project on these and other similar graphs last summer. It is easy to state, and it would not surprise me if the answer were known.

First, the background.

The commuting graph of a non-abelian group G has as vertices the non-central elements of G, two vertices joined if they commute.

The reason for restricting to non-central elements is because classically the most important question is whether the graph is connected. The prime graph of a finite group G has as vertices the prime divisors of |G|, two vertices p and q being adjacent if there is an element of order pq in G. The connectedness of this graph is important in group cohomology; my former colleague Karl Gruenberg worked on this. Now it can be shown that the prime graph is connected if and only if the commuting graph is connected. If we allowed central elements as vertices, then any two vertices would be joined by a path of length 2 via the centre, and the above equivalence would not be true.

Let us take symmetric groups as an example. If neither n nor n−1 is prime, then the commuting graph of Sn is connected. The proof goes like this:

  • Transpositions with disjoint support commute, and so are joined.
  • Since n≥5, if the supports of two transpositions intersect, there is a transposition disjoint from both, so they lie at distance 2.
  • If g fixes at least two points, then it is joined to some transposition.
  • If g fixes at most one point, but has more than one non-trivial cycle, then it commutes with one of its cycles, which fixes at least two points.
  • If g fixes at most one point and has a single non-trivial cycle, then by assumption its order is not prime, so some power of g (which commutes with g) has more than one non-trivial cycle.

This shows that the commuting graph has diameter at most 8 (this can be improved slightly). Also, if either n or n−1 is a prime p, then an element of order p commutes only with its powers; these form a connected component which is a complete graph. So in general, all components can be described.

The problem is:

Does the commuting graph of G determine the order of G?

Here are a few comments. First, knowing the number of vertices of the commuting graph does not suffice. For example, there are groups with orders 32, 36 and 40, having centres with orders 2, 6 and 10 respectively; in each case the commuting graph has 30 vertices.

Suppose that the commuting graph has n vertices, and that the centre of G has order z (so G has order n+z). Then:

  • By Lagrange’s Theorem, z divides z+n; so z divides n.
  • Let c(g) be the size of the closed neighbourhood of g (that is, g and its neighbours. Then the centraliser of g has order z+c(g). Thus we get a refinement of the first point: z divides z+c(g), which in turn divides z+n.
  • Call two vertices equivalent if their closed neighbourhoods are equal. Then each equivalence class is a union of cosets of the centre, so z divides its size.
  • The group acts on its commuting graph by conjugation; elements of the centre fix everything, while g has c(g) fixed points. So z+n divides zn plus the sum of the sizes of the closed neighbourhoods.

Can all this information be used to determine z?

Here is a very simple example. The groups C11×S3 and C5×A4 each have commuting graphs with 55 vertices. For the first of these, the graph is the union of a complete graph of size 22 and three complete graphs of size 11. The first point shows that z divides 55. The second shows that z divides both 11 and 22, while z+11 divides 44 and z+22 divides 33. There is more than enough information here to show that z = 11.

You might wonder if more is true: perhaps the commuting graph determines the group up to isomorphism? It doesn’t: for each of the two non-abelian groups of order 8, the commuting graph consists of three disjoint edges.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics. Bookmark the permalink.

5 Responses to Commuting graph

  1. Thanks for a great post, I’ve been thinking about commuting graphs and this has answered a lot of my questions.

    My interest in these graphs comes from studying the right angled Artin groups (RAAGs). The functor assigning a RAAG to a graph is left adjoint to the functor assigning the commuting graph (with centre) to a group. My personal preference is to keep the centre in the graph so that the construction is functorial.

    So the adjunction means that given a graph B and a group H, the set of homomorphisms Hom(A_B, H) from the RAAG of B to H is isomorphic to the set of (possibly degenerate) subgraphs isomorphic to B inside CG(H), the commuting graph of H.

    An application of this gives us an action of Aut(A_B) on the set of subgraphs isomorphic to B inside CG(H). So these graphs really do have a lot of structure!

    I’ll have to read up on the prime graph, I’ve not met it before. The connectivity result is very interesting.

    • Thanks for this. I agree that probably the convention about excluding central elements from the commuting graph would never have been made if it were not for the connection with interesting questions about connectedness of the prime graph; and the question I raised is a non-question if central elements are included (and perhaps one might feel that it should remain so!)

  2. Colin Reid says:

    There’s an amusing result on the subject of finite groups without elements of order pq for given p and q. Essentially, at least one the relevant Sylow subgroups must be abelian… unless the Monster group shows up as a quotient!

    In other words, with a couple of strange exceptions there must be enough abelian Sylow subgroups to touch all the non-edges of the prime graph. I don’t know how much this helps with the commuting graph though.

  3. Colin Reid says:

    I found a paper that answers the problem in the negative:

    Mogkhaddamfar, A. R.
    On noncommutativity graphs. (Russian. Russian summary) Sibirsk. Mat. Zh. 47 (2006), no. 5, 1112–1116; translation in
    Siberian Math. J. 47 (2006), no. 5, 911–914

    The example in this paper shows we cannot determine the power of 2 dividing the order. One weaker question would be: can we tell the parity of the order of G from its commuting graph? (Obviously this is only in question if n is even.)

  4. I should have mentioned that the Masters student involved was Linh Nguyen. She graduated with distinction from Kings on Wednesday this week. I hope to post a picture sometime when she sends me one.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s