Graphs on groups, 8

The dark clouds seem to have lifted a bit. Perhaps now, that the last rush of conferences for a while is over, life can return to something like normality …

For me the most significant event was the last in the series of research discussions on graphs and groups, run by Vijayakumar Ambat and Aparna Lakshmanan S. in CUSAT, Kochi. The whole series was a great success. I gave the last talk, and devoted it to describing five areas, mostly involving the power graph of a group, where significant progress has resulted, usually as a result of contacts made during the RDGG meetings. In fact, almost as soon as I had given the talk, it was outdated: Swathi V V and I had answered, in a way which came as a surprise to me, one of the questions I asked in my talk. (This is described below.) Anyway, as well as getting the slides from the usual place on my St Andrews web page, you can watch videos of any or all of the talks in the discussion group. The link is https://youtube.com/playlist?list=PLemEI0kNLyjsrc95V78CQs3go-1sPS15T.

Another very nice meeting that I didn’t have the time or energy to comment on before was the 80th meeting of the Portuguese Mathematical Society. I was invited to speak, and chose a topic which I hoped would be accessible to many participants: “Conversations between graphs and groups”. I chose four areas where these two rather different parts of mathematics have interacted fruitfully. Again, the slides are in the usual place, and the professionally produced video is available from https://m.youtube.com/watch?v=OlELf0jBpPM&feature=share.

Anyway, here is a description of the new result. I have been banging on for a while about a hierarchy of graphs whose vertex set is a given group. I will only need two of them here:

• the power graph, in which x and y are joined if and only if one is a power of the other;
• the enhanced power graph, in which x and y are joined if they are both powers of some element z (equivalently, if the group they generate is cyclic).

Obviously any edge of the power graph is an edge of the enhanced power graph; said otherwise, the power graph is a spanning subgraph of the enhanced power graph. The two graphs coincide if and only if the group has the property that every element has prime power order. These are the so-called EPPO groups, which have been classified.

As a generalization of the classification of EPPO groups, I posed the following general problem. Let f be a graph parameter which is monotone, in the sense that adding edges to a graph doesn’t decrease its value. Then the value of f on the power graph of a group G is less than or equal to its value on the enhanced power graph. If these two graphs coincide, the values will be equal. But easy examples show that they may be equal for a wider class of groups. So I proposed the question: given a monotone graph parameter f, for which groups G do its values on the power graph and enhanced power graph coincide? This will be a wider class than the class of EPPO groups, and of course it depends on the chosen parameter.

An example of a monotone graph parameter is the matching number μ(Γ), defined to be the largest cardinality of a matching, a set of pairwise disjoint edges of the graph. Now our theorem says the following: the class of finite groups for which the power graph and enhanced power graph have equal matching number is the class of all finite groups!

Here is a hint at the proof. Take a matching M of maximum cardinalitly in the enhanced power graph of a group G. If all edges in M belong to the power graph, we are done; so suppose not. We are going to replace M by another matching of the same size, with one fewer edge not belonging to the power graph; after finitely many such steps we will be done.

Choose an edge {g,h} which is in M but is not an edge of the power graph, and (subject to this) the least common multiple of the orders of g and h is as large as possible. This lcm, call it l, is equal to the order of the cyclic group C generated by g and h. Now C has φ(l) generators, say x₁,…,x_φ(l), each of which is a dominating vertex of the induced subgraph on C, that is, joined to all other vertices. (Here φ is Euler’s totient.) If one of these vertices, say x_i, is not covered by M, then we can replace the edge {g,h} by the edge {g,x_i), which belongs to the power graph; so we can assume that there are elements y₁,…y_φ(l) such that, for all i, {x_i,y_i} is in the matching M.

Now there are three possibilities for such an edge:

• x_i; is a power of y_i;
• y_i is a power of x_i;
• neither of the above.

In the first case, g and h are powers of y_i, so we can replace the edges {g,h} and {x_i,y_i} by {g,x_i} and {h,y_i}, both in the power graph. In the third case, the least common multiple of the orders of x_i and y_i is greater than l, contradicting the choice of {g,h}.

So the second case must apply for all values of i, and the vertices y₁,…y_φ(l) belong to C. If any two of them, say y_i and y_j, are joined in the power graph, then we can do a three-way swap, replacing {g,h}, {x_i,y_i} and {x_j,y_j} by {g,x_i}, {h,x_j} and {y_i,y_j}.

So we have an independent set of size φ(l) in the cyclic group of order l. But, using elementary number theory, it can be shown that this is only possible for l ∈ {2,6}, and these cases are easily dealt with.

So, a quick question: Let φ be Euler’s function and τ the divisor function. Then φ(n) > τ(n) unless n is one of the numbers 1, 2, 3, 4, 6, 8, 10, 12, 18, 24, 30. Is this written down anywhere? (If you haven’t seen it, it is an interesting exercise.)