Graphs on groups, 9

We continue to make progress with the graphs on groups project, but this post attempts to step back and look at the whole thing.

What use is all this?

Once, after I talked at a departmental colloquium at the University of Southern California, after my talk someone asked “What use is all this?” My view is that the fact that it is fun is reason enough to do it. But people like funders may want more than that as an answer. So let me make some comments.

To group theorists

A group theorist is likely to ask: What do I learn about a group from these graphs? So I will address that first.

The subject began with the seminal paper of Brauer and Fowler in 1955, in which they showed that there are only finitely many finite simple groups having a given group as the centralizer of an involution. Of course, it wasn’t then known that a non-abelian finite simple group must contain an involution; at the time, this was “Burnside’s conjecture”, and was proved by Feit and Thompson in the next decade. After Brauer–Fowler and Feit–Thompson, it was clear that characterizing simple groups by the centralizer of an involution would be an important ingredient in any eventual classification; and so indeed it turned out.

Brauer and Fowler used the reduced commuting graph (the commuting graph with the identity removed). I think the word “graph” does not occur in their paper, but the make use of the graph distance. Essentially they showed that the distance between two involutions in this graph is rather small.

Maybe the next contribution was that of Gruenberg and Kegel, who defined the prime graph of a finite group (now called the Gruenberg–Kegel graph: the vertices are the prime divisors of the group order, two vertices p and q joined if there is an element of order pq in the group. They gave a powerful structure theorem for groups whose GK graph is disconnected. Moreover, this was a tool in studying the decomposition of the augmentation ideal of the integral group ring.

I will return to this question later.

Another thing of interest to group theorists is that questions about the graphs often give rise to challenging problems about the groups. Here are three examples.

1. The following three properties of a finite group G are equivalent:
   • G is an EPPO group (all elements have prime power order);
   • the Gruenberg–Kegel graph of G has no edges;
   • the power graph and enhanced power graph of G coincide.
   So we have the problem of classifying these groups.
2. Other questions about when two of these graphs coincide give rise to other group-theoretic classification problems, some of which are worth a look. Examples include minimal non-abelian, non-nilpotent, or non-solvable groups, 2-Engel groups, and Dedekind groups.

To graph theorists

By contrast, graph theorists are not going to learn anything about general graphs by studying graphs derived from groups. However, there is a different motivation, cited by Kelarev and Quinn when they introduced the power graph in around 2000: Do groups give us examples of graphs with interesting properties, for example, graphs which will be good as networks (so good connectivity and expansion properties)?

In looking for a good network, there is a tension between having many edges (which will make the network more expensive to construct) and having good connectivity (too few edges work against this). I don’t know any definitive result. But when I was involved in writing a survey paper on power graphs of groups, as an experiment I looked at an example, the Mathieu group M₁₁, the smallest sporadic simple group. This group has order 7920, so we start with a graph with 7920 vertices. But simple reductions (first “twin reduction”, identifying vertices with the same open or closed neighbourhood, then discarding “peripheral” parts of the graph) results in a rather beautiful graph: a bipartite graph on 165+220 vertices, which is semiregular (valencies 4 and 3 in the two parts), has diameter and girth 10, and has automorphism group M₁₁. I have not examined this graph further, and have not done a thorough search to see if it has been found before, but finding something as nice as this in the first place I looked seemed a good omen.

To other mathematicians

I can offer here, as a carrot, the fact that this research has thrown up a number of interesting diophantine problems in number theory.

For one example among many, the power graph and enhanced power graph of a group have the same clique number if and only if the largest order of an element of the group is a prime power. I do not expect that much can be said about this class of groups. But let us look at one example, the groups PGL(2,q) for prime powers q. The largest order of an element in this group is q+1. So the power graph and enhanced power graph have the same clique number if and only if either

• q is a power of 2, and q+1 is a Fermat prime or 9; or
• q is a Mersenne prime, and q+1 is a power of 2.

(The first bullet point here conceals the use of the solution to Catalan’s equation, prime powers differing by 1.)

Other number-theoretic problems are thrown up by other questions. But here is one which is unrelated.

A clique in the power graph of G is contained in a cyclic subgroup of G. So the clique number of the power graph of G is equal to the largest clique number of a cyclic subgroup of G. (This is not the same as the clique number of the largest cyclic subgroup.) Now the clique number of a cyclic group of order n is a number-theoretic function f which is defined by the recurrence f = 1, and for n > 1, f(n) = φ(n)+f(n/p), where p is the smallest prime divisor of n, and φ is Euler’s totient. It follows that f(n)<3φ(n) for all n. But we could ask:

• Is the lim sup of the ratios f(n)/φ(n) rational, algebraic, or transcendental?
• What other limit points does the set of these ratios have?

To young researchers

Finite group theory is a very technical area, often somewhat off-putting to outsiders. But graph theory is vast and sprawling with many easy ways in.

So, not surprisingly, the field of graphs on groups offers many problems where mathematicians starting out can work profitably.

For example, there are many graphs defined on groups: power graph, enhanced power graph, deep commuting graph, commuting graph, nilpotence graph, solubility graph, non-generating graph. In a paper in preparation, we are going to extend this hierarchy into a second dimension. And there are many graph properties and parameters: connectedness, diameter, girth, clique number, chromatic number, independence number, clique cover number, matching number, domination number (strong or weak), Eulerian, Hamiltonian, pancyclic, and lots more.

So choose a type of graph on a group, and a property or parameter; chances are reasonably good that this will not previously have been investigated. See what you can do!

There are other areas of algebra where similar graphs arise, and where similar questions can be asked. One of these is zero-divisor graphs of rings (that is, commutative rings with identity).

Some of my favourite problems

Since we have a hierarchy, which is being extended into a second dimension, one very natural thing is to compare two graphs in the hierarchy. Most questions about the original hierarchy have been solved, and interesting graph classes arise. But there will soon be more such questions.

Also, even if these problems have been solved, they can be generalized in the following way. Take two adjacent graphs in the hierarchy, call them A and B; and take a monotone graph parameter p, one which cannot decrease when an edge is added (or one which cannot increase, if you prefer): many parameters are monotone. Now ask: For which groups G does p(A(G)) = p(B(G))? Two small examples: the clique numbers of the power graph and enhanced power graph of G are equal if and only if the largest order of an element of G is a prime power; and the matching numbers of these two graphs are equal for all G (even though we cannot write down a formula for them in every case).

Another problem area concerns universality. Given a graph type A, can every finite graph be embedded as induced subgraph in A(G) for some group G? If not, can you identify the class of graphs which can be so embedded? And in the other direction, given a subgroup-closed class of graphs, can you identify the class of groups G for which A(G) belongs to that class?