## Graphs on groups, 12

One thing I have learned from the project is that the most interesting question about graphs defined on groups is this: given two types of graph defined on a group G, what is the class of groups for which the two graphs are equal? Answering this question has already thrown up some famous and important classes of groups, as I discussed earlier, including Dedekind groups, 2-Engel groups, EPPO or CP groups, and groups with all Sylow subgroups cyclic or generalised quaternion.

Now I am happy to report on another instance, where it is not so much the class of groups which is important as the group-theoretic methods used to obtain the result. The authors are Saul Freedman, Andrea Lucchini, Daniele Nemmi, and Colva Roney-Dougal. I’m grateful to them for keeping me in the loop with this project.

The story begins with the generating graph of a group, in which two elements are joined by an edge if together they generate the group. This has been of very great importance since its introduction by Breuer, Guralnick and Kantor, especially in connection with the probability that two random elements generate the group. But it is not much use for groups which cannot be generated by two elements!

Andrea Lucchini proposed using a different graph which does not have this defect. Call two elements x and y of the group G independent if there is no minimal (with respect to inclusion) generating set for G containing both of them. The independence graph of G has vertex set G; its edges are the independent pairs.

There is an obvious obstruction to being joined in this graph; namely, being joined in the power graph. If, say, y is a power of x, then no minimal generating set can contain both, since if they both lie in a generating set then deleting y results in a smaller generating set. So the independence graph is a subgraph of the complement of the power graph.

Lucchini says that a group G has the independence property if the independence graph is equal to the complement of the power graph. Now the theorem which has been proved by these four authors gives a complete classification of groups with the independence property; all are supersoluble.

The bulk of the proof concerns a hypothetical insoluble group with the independence property. Four pages of argument reduce this to the case of an almost simple group, and then thirteen pages of very detailed analysis of the finite simple groups and their automorphism groups (including special consideration of the 8-dimensional orthogonal groups of type + over fields of orders 2, 3 and 5) shows that none of these can occur. Even after all this, and it is known that the group must be supersoluble, it requires another five pages to complete the classification.

The key result about almost simple groups, important in its own right and almost certainly having further applications, is the following. Any non-abelian finite simple group S contains two non-commuting elements s and x such that, in any almost simple group G with socle S, the element x lies in every maximal subgroup containing s. In most cases the element x can be chosen to normalise the subgroup generated by s. But this gives only the barest indication of the level of detail required.

The paper also contains a similar but much easier result, which was actually proved at my suggestion. The rank of a finite group is the minimum number of generators, and two elements are rank-independent if they are contained in a generating set whose cardinality is equal to the rank. The rank-independence graph has two elements adjacent if they are rank-independent. Now the obvious obstruction to adjacency in this graph is adjacency in the enhaced power graph. (For suppose that x and y are joined in the enhanced power graph; this means that there is an element z such that both x and y are powers of z. Now if such a pair is contained in a generating set S, then we may remove x and y and insert z instead to obtain a strictly smaller generating set.

Call a group G rank-perfect if the rank-independence graph is the complement of the enhanced power graph. The paper also shows that rank-perfect groups are supersoluble, and gives a complete classification of them; the entire argument takes just over two pages.

Answering a question always opens many more. For most groups, there is a “gap” between the complement of the power graph amd the independence graph, or between the complement of the enhanced power graph and the rank-independence graph. What can be said about these difference graphs? For example, which vertices are isolated, or joined to all others? When are these graphs connected?

Also, what is the relation between the independence graph and the enhanced power graph, or the commuting graph? And what is the relation between the rank-independence graph and the commuting graph? I mean, for which groups is the intersection of one of these pairs the null graph, and for which groups is the union the complete graph? Other questions of the same sort can also be asked.