Last week Chris Parker gave a very interesting talk in the London Algebra Colloquium on this topic. It is an excellent example of a curious phenomenon. If you look for your keys under the lamppost, then in a Borgesian way you are likely to find them there, even if more interesting things are lurking in the darkness away from the lamp.
The commuting graph of a finite group G has as vertex set the elements of the group, two vertices x,y being joined if xy = yx. If G is abelian, this is a complete graph, so we are interested in non-abelian groups.
The concept was first investigated by Gruenberg and Kegel, in connection with their work on relation modules. They were interested in connectedness and diameter of the commuting graph. But, as I defined it above, even if xy ≠ yx, there is a path of length 2 from x to y, where the intermediate vertex is the identity. So, to make the question interesting, we should remove from the graph all elements which commute with everything, that is, the centre Z(G) of the group. The resulting graph is what is now called the commuting graph of G, and denoted by Γ(G), and is the graph of interest to Gruenberg and Kegel.
They showed that the commuting graph is connected unless G is a Frobenius group, a 2-Frobenius group, or almost simple, and posed the question of bounding the number of connected components. The question of bounding the diameter in the connected case (or more generally, the diameter of any component) is also interesting; Popinchuk, Segev and Seitz used results on this to show that a finite quotient of the multiplicative group of a finite-dimensional division algebra is soluble.
A fairly typical example is given by the symmetric group of odd prime degree p. The p−1 non-identity powers of a p-cycle commute only with one another, and form a connected component which is a complete graph on p−1 vertices. All the other elements lie in a single, rather complicated, component, whose diameter is known to be at most 5.
More recently, Morgan and Parker showed that, if G is a group with Z(G) = 1, then the diameter of every connected component is at most 10. This was the end of a long line of research, in the course of which Jafarzadeh and Iranmanesh were led to conjecture that, if the commuting graph is connected, then its diameter is bounded.
As usual in problems of this type, the strategy is to reduce the problem to one about simple (or almost simple) groups, and then use the “lamppost” of modern finite group theory, the Classification of Finite Simple Groups. This strategy led eventually to the definitive result of Morgan and Parker mentioned above.
An example by Hegarty and Zhelezov of a 2-group whose commuting graph has diameter 10 gave a hint that the conjecture might be false, and the solution might be found in an entirely different direction. And so it turned out, when a remarkably simple (in the other sense) counterexample was found by Giudici and Parker.
Their example is a special 2-group. The construction of such a group involves two vector spaces V,W over the field GF(2) and a cocycle from V to W. This is a function f : V×V → W satisfying some condition which I won’t write down; the group is then defined to be the set V×W, that is, the set of all ordered pairs (v,w) with v∈V and w∈W, with the group operation given by
(v1,w1)•(v2,w2) = (v1+v2,w1+w2+f(v1,v2)).
The “cocycle condition” is precisely what is needed to make this operation associative.
Giudici and Parker take V and W to have dimensions m and m−2 respectively, with bases x1,…,xm and y1,…,ym−2 respectively. The cocycle is defined on the basis vectors by the rule that f(xi,xj) is equal to 0 if j < i+2, and is yj−i−1 otherwise; the definition is then extended to the other vectors using bilinearity. They show that this is a cocycle, and that the commuting graph of the resulting group has diameter at least m−1.
The moral of the story is that, even though CFSG is our best tool for understanding finite groups, it remains true that most finite groups are 2-groups, whose understanding requires completely different tools.