Graphs defined on groups

Apologies; I have been so busy lately that very little has got written up. Let me try to remedy this with a quick tour through some recent mathematical developments.

As some of my posts have hinted, one topic I have been much involved with is graphs defined on groups, typically things like the commuting graph, generating graph, and power graph. This came about for a couple reasons, both emanating from India. First, Angsuman Das at the Presidency University in Kolkata asked me to speak at an International Conference on Algebraic Graph Theory and Applications on this topic. While I understand the main part of Algebraic Graph Theory to concern study of eigenvalues and automorphism groups of graphs, I know that there are a number of people in India and elsewhere who are interested in these specific topics. I was asked to give a 90-minute expository talk. So I had a bit of reading up to do.

At about the same time I had an email from Ranjit Mehatari in Rourkela enclosing a preprint of some recent research and asking for suggestions on new research topics. As I have discussed, this led to some new ideas about questions of the general form: for which groups G does the power graph of G have certain specified properties? You can read the resulting preprint on the arXiv, but here are two particular questions which seem of interest.

1. The power graph of a finite group (two vertices joined if one is a power of the other) is always a perfect graph. What about the enhanced power graph (two vertices joined if they generate a cyclic group) or the commuting graph (two vertices joined if they generate an abelian group)? For which groups is each of these a perfect graph? This has not been much studied, and is I think of interest.
2. For which groups G is the power graph of G a cograph (that is, does not contain the 4-vertex path as induced subgraph)? We know the answer for nilpotent groups, but the general case is open.

While preparing my talk for Kolkata, I was struck by the fact that the Gruenberg–Kegel graph of a finite group carries a lot of information about several of these graphs. This graph has as vertex set the set of prime divisors of the group order, with an edge from p to q if and only if the group contains an element of order pq. So it is very much smaller than the graphs defined on the group! Now:

1. For groups with trivial centre, the commuting graph is connected if and only if the GK graph is connected.
2. The power graph is equal to the enhanced power graph if and only if the GK graph is a null graph (that is, has no edges).
3. There is a necessary condition, and a sufficient condition, for the power graph of G to be a cograph, both phrased in terms of the structure of the GK graph – but there is no necessary and sufficient condition depending only on the GK graph.

While thinking about the second of the above, I wrote to Natalia Maslova to ask if she had a list of groups with this property. She was able to work it out, and we hope to make all this available shortly.

But in the meantime we turned our attention to another problem about the GK graph. We were able to show the following. There is a function F with the property that, given a finite graph Γ, if the number of groups with GK graph isomorphic to Γ is greater than F(n), where n is the number of vertices, then it is infinite. Moreover, F is bounded by a polynomial (of degree 7 in our proof, though no doubt some improvements could be made). The paper has just gone on the arXiv.

A chance remark from Natalia in this connection led me in a completely different direction, which I have been working out with Bojan Kuzma. We have defined a new graph which lies between the enhanced power graph and the commuting graph. We call it the deep commuting graph. The definition looks a bit abstruse. It depends on the notion of a Schur cover of G, a group H with a subgroup Z such that H/Z is isomorphic to G, and Z is contained in both the centre and the derived group of H; moreover, H should be as large as possible subject to this. Now we say that x and y are joined in the new graph if and only if their inverse images in H commute. (Since Z is central in H, this condition does not depend on the choice of coset representatives of Z.)

A given group can have several different Schur covers, but they cannot be too different; the subgroups Z are all isomorphic (this is the Schur multiplier of G); and the graphs defined on G by the above procedure are all isomorphic. However, a frustrating open problem remains. We do not know whether the graphs on G defined by different Schur covers are all equal (that is, have the same edge sets), even though they must be isomorphic, and must lie between the enhanced power graph and the commuting graph.

We also have necessary and sufficient conditions for our new graph to be equal to either the enhanced power graph or the commuting graph. Equality in the latter case holds if and only if the Schur multiplier is equal to the Bogomolov multiplier: this is a lesser-known group-theoretic construction which arose first in studying rationality questions in invariant theory. A paper should be on the arXiv shortly.

And finally for this post, St Andrews PhD student Saul Freedman (of whom I am second supervisor) has been looking further up the hierarchy. If G is non-abelian or not 2-generated, the commuting graph is a spanning subgraph of the non-generating graph, in which x and y are joined if together they do not generate the whole group. The edge set of this graph is the union of complete graphs on the maximal subgroups of G. Saul has been looking at the difference between this and the commuting graph, which we call by the less than snappy (but descriptive) title non-commuting non-generating graph – x and y are joined if they don’t commute but don’t generate the group. He has very strong results on various properties of this graph, especially its connectedness (apart from the identity); the answer for nilpotent groups is particularly complete and a paper is on the arXiv.

In addition, Saul used rather similar techniques to study the intersection graph of a group G, whose vertices are the non-trivial proper subgroups of G, two subgroups joined if they have non-trivial intersection. It was known to be connected, but for simple groups the best upper bound for the diameter was 28. Saul has reduced this to the best possible value, namely 5.

The value 5 is realised by the Baby Monster and by some unitary groups. The diameter of the intersection graph of a simple unitary group is 3, 4 or 5, and all values occur; we do not currently know which groups have which diameters.