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 p3 and exponent p2. This is generated by two elements a and b, where a has order p2, b has order p, and the commutator [a,b] is equal to ap.

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 {vi,vn} is red, then replace vi by (1,vi);
  • if {vi,vn} is green, then replace vi by (ap,vi);
  • if {vi,vn} is blue, then replace vi by (a,vi).

Finally, we embed vn 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 = ap, 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.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, mathematics and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.