Induced subgraphs of power and commuting graphs

For those who like thinking about these things, here is a small observation and a few problems.

As I have recently discussed, the power graph of a group is perfect. This means that all its induced subgraphs are perfect, and in particular they all have clique number equal to chromatic number.

Problem 1 Is every perfect graph an induced subgraph of the power graph of some group?

For the commuting graph, things are different: every finite graph is an induced subgraph of the commuting graph of a group. To see this we use the following simple construction. Let V be a vector space over the field F with two elements. Let B be a bilinear form on V. Define an operation on V×F by the rule

(v,a) * (w,b) = (v+w,a+b+B(v,w)).

It is easily checked that this is a group operation. Now let {v1,…vn} be a basis for V. The values of B(vi,vj) can be prescribed arbitrarily, and the resulting function extended to V×V by bilinearity. So, given a graph on the vertex set {1,…n}, put B(vi,vj) equal to 0 if i ≤ j, while for i > j put the value equal to 0 if i and j are joined, 1 otherwise. This works because the commutator of (v,0) and (w,0) is (0,B(v,w)+B(w,v)).

Problem 2 Given a graph on n vertices, consider the group defined above. Which other graphs can be realised by changing the basis for V?

It follows that, for every n, there is a group whose commuting graph contains every n-vertex graph as an induced subgraph.

Problem 3 What is the smallest group G with this property?

Problem 4 Is every graph an induced subgraph of the enhanced power graph of a group?

Problem 5 Is every graph an induced subgraph of the generating graph of a 2-generator group?

About Peter Cameron

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

3 Responses to Induced subgraphs of power and commuting graphs

  1. Problem 1 is now solved.
    Power graphs are comparability graphs of partial orders; this is a more restrictive class than perfect graphs. But every comparability graph of a partial order is an induced subgraph of a power graph. Here is the argument.
    First, every partial order can be represented as the induced suborder of the subsets of a set. (Take the set to be the set of elements of the partial order, and represent x by the set of elements less than or equal to x.) Now consider the partial order on a set of subsets of an n-element set. Take G to be the direct product of cyclic groups whose orders are n distinct primes. Represent each subset by the product of generators of the cyclic groups whose orders are the corresponding primes.

    If you know about the deep commuting graph (see https://arxiv.org/abs/2012.03789 if you don’t), every graph is an induced subgraph of the deep commuting graph of a group. I won’t tell you why; it is a pleasant exercise working it out.

    So here is a problem to replace Problem 1. A very general problem.
    Problem 6 Pick your favourite class of groups (nilpotent groups, simple groups, etc.) Pick one of the above graphs (power graph, commuting graph, etc.) Which graphs are induced subgraphs of that graph of a group in your class?
    I mention one fact: every graph is an induced subgraph of the commuting graph of a nilpotent group of class 2 and exponent 4. (That is what the proof in the post above shows.)

  2. Problem 4 is also solved. I thought this might be an interesting case, since the enhanced power graph is so closely related to the power graph; but indeed every finite graph is an induced subgraph of the enhanced power graph of some group.

    This leaves the interesting case of the generating graph still open.

    So, again, here is another problem.
    Problem 7 The power graph is contained in the enhanced power graph, which is contained in the deep commuting graph, which is contained in the commuting graph, which (if the group is nonabelian) is contained in the non-generating graph. Take any two of these and look at their difference. Which finite graphs occur as induced subgraphs in this difference graph for some group?

  3. The last case is done: Any finite graph is isomorphic to an induced subgraph of the generating graph of a finite group. Proof later.

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.