Graphs on groups, 2

I wrote the long post about this to try to write it out of my system. No luck …

I mentioned in that survey that every finite graph is embeddable as induced subgraph in the enhanced power graph, deep commuting graph, commuting graph, or non-generating graph of some finite group. The proofs are all different and require a small amount of ingenuity.

If we start thinking about differences, several further questions arise. For example, the groups I use to show that enhanced power graphs are universal are all abelian, and so in fact (by looking at complements) we see that graphs on groups whose edge sets are the differences of the commuting graph and enhanced power graph are universal.

In fact, with a little more ingenuity, much more can be shown.

Suppose that we have a finite complete graph on n vertices, whose edges are coloured with three colours, say red, green and blue, in any manner. Then we can embed the vertex set in a finite group G in such a way that

• two vertices joined by a red edge are adjacent in the enhanced power graph;
• two vertices joined to a green edge are adjacent in the commuting graph, but not in the enhanced power graph;
• two vertices joined by a blue graph are non-adjacent in the commuting graph.

In other words, the structures with three kinds of pair, enhanced power graph, commuting graph minus enhanced power graph, and non-commuting graph, are universal for finite structures of this kind.

Here is the proof. If p is an odd prime, we make use of the group P, the non-abelian group of order p³ and exponent p². This is generated by two elements a and b, where a has order p², b has order p, and the commutator [a,b] is equal to a^p.

The proof is by induction on n, the result being clear if n = 1. So suppose that n > 1, and that we have embedded the first n−1 points into a group G so that the three conditions hold. Choose a prime p which does not divide the order of G, and let P be the group defined above. We modify this to get an embedding into the direct product P×G as follows:

• if {v_i,v_n} is red, then replace v_i by (1,v_i);
• if {v_i,v_n} is green, then replace v_i by (a^p,v_i);
• if {v_i,v_n} is blue, then replace v_i by (a,v_i).

Finally, we embed v_n as the element b.

Then this gives an embedding of the whole n-element structure.

The proof is not so hard, depending on three simple observations:

• the direct product of cyclic (resp. abelian) groups of coprime order is cyclic (resp. abelian);
• two elements lying in ⟨a⟩ generate a cyclic group;
• b and x generate a cyclic group if x = 1, a non-cyclic abelian group if x = a^p, and a non-abelian group if x = a.

Obviously there are a number of variants on this using other types of graphs in the hierarchy. Please try one problem of this kind for yourself; or, less ambitiously, take the difference between two types of graph in my hierarchy and decide whether it is universal, and if not, which graphs can be embedded as induced subgraphs.