Groups and graphs

Two new preprints have appeared on the arXiv (2008.09291 and 2009.02884), about which I would like to say something. One is by Saul Freedman, the other by him and two co-authors (his PhD supervisors).

The intersection graph of a group G is the graph whose vertices are the proper non-trivial subgroups of G, two vertices joined if they have non-trivial intersection. (Here, as usual, the trivial subgroup of any group is the subgroup whose only element is the identity of the group. For obvious reasons we exclude the cyclic groups of prime order.) The history of this graph is explained in the preprint on the arXiv. It was defined by Csákány and Pollák in 1964; they determined the non-simple groups for which it is disconnected, and proved that if it is connected (for non-simple G), then its diameter is at most 4.

What about simple groups?

In 2010, Shen proved that the the intersection graph is connected and asked for an upper bound on the diameter. In the same year Herzog, Longobardi and Maj gave a bound of 64. This was reduced to 28 by Ma in 2016. Meanwhile Shasavari and Khosravi gave a lower boud of 3.

Now Saul has reduced the upper bound to 5; shown that this is best possible (the intersection graph of the Baby Monster has diameter 5, the distance 5 realised by two subgroups of order 47), and shown moreover that any other simple group whose intersection graph has diameter 5 must be a simple unitary group of odd prime degree. There exist unitary groups where the diameter is 5, and others where it is 4; we do not currenly have a complete classification.

So let me interpolate a question here which is relevant to this and may be interesting to finite geometers. The classical unital U(q), for a prime power q, has q³+1 points, and the unitary group PGU(3,q) acts on it 2-transitively. This group has a cyclic subgroup of order q²−q+1, which acts with q+1 regular orbits. Is the following true? If O is one of these orbits, and g is any element of PGU(3,q), then O and Og have non-empty intersection.

The other paper turns to territory more familiar to me. Consider the following graphs whose vertices are the non-identity elements of a group G:

• the power graph, with x joined to y if one is a power of the other;
• the enhanced power graph, with x joined to y if both are powers of an element z;
• the commuting graph, with x joined to y if xy = yx;
• the non-generating graph, with x joined to y if x and y do not generate G;
• the complete graph, with all pairs adjacent.

Each graph is a spanning subgraph of the following one, except possibly for the third and fourth, for which this holds if G is non-abelian.

When can it happen that two consecutive graphs on this list coincide? For the first and second, and for the second and third, this question was answered in a paper I wrote with Ghodratollah Aalipour, Saieed Akbari, Reza Nikandish, and Farzad Shaveisi in 2017, using classical results of Frobenius, Burnside, Zassenhaus, and Gruenberg and Kegel, among others. For non-abelian G, the third and fourth are equal if and only if G is minimal non-abelian (all proper subgroups abelian); these groups were classified back in 1903 by Miller and Moreno. The last pair are equal if and only if G cannot be generated by two elements.

The next question one might ask about this hierarchy (assuming G non-abelian) is whether successive differences are connected, and what can be said about the diameter of connected components. For the last pair, the difference is the generating graph of the group, in which two vertices are joined if together they generate the group. This graph has received a lot of attention, not least from Scott Harper (a St Andrews graduate); a recent theorem of his with Tim Burness and Robert Guralnick shows that if G is finite and all proper quotients of G are cyclic, then the generating graph has diameter 2 (arXiv 2006.01421).

The next difference is the so-called non-generating, non-commuting graph; this is the graph considered in Saul’s other preprint. I won’t describe here the results (which chiefly concern connectedness and diameter in the case where G is nilpotent, though there is much more in Saul’s thesis), since I want to add some further comments to the general set-up.

Firstly, after examining connectedness and diameter, one could ask questions such as Hamiltonicity, clique size, chromatic number, domination number, and so forth. However, for the first two “difference graphs”, even the question of connectedness is open. (The connectedness of the commuting graph has been much studied, but this is the edge-union of the first three of the difference graphs.)

A second comment is that, if G is non-abelian and 2-generated, then we have partitioned the complete graph on the non-identity elements of G into (at most) five parts. What happens if we run the Weisfeiler–Leman algorithm on this partition, to find the coarsest coherent configuration refining it?

For the final comment, note that in the enhanced power graph, two vertices are joined if and only if they generate a cyclic group; in the commuting graph, if and only if they generate an abelian group; and in the non-generating graph, if and only if they generate a proper subgroup. This inevitably suggests many further graphs, defined by imposing an appropriate condition on the subgroup generated by the two elements, either intrinsic (e.g. nilpotent or soluble) or with relation to the whole group. This opens a large number of problems. Are any of them interesting? Perhaps the best way to find out is to study them and see!