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.