Perfectness of commuting graphs

A finite graph is perfect if the clique number and chromatic number of any induced subgraph are equal. The main facts about perfect graphs are:

  • (The Strong Perfect Graph Theorem) A graph is perfect if and only if it has no induced subgraph which is an odd cycle of length at least 5 or the complement of one.
  • (The Weak Perfect Graph Theorem) If a graph is perfect then so is its complement.

In recent postings I defined the power graph and the commuting graph of a finite group. In the case of the commuting graph, central elements of the group were excluded; here it won’t matter if they are excluded or not. If we include them, then the power graph is a spanning subgraph of the commuting graph. (This is just a fancy way of saying that if one element is a power of another then the two elements commute.)

The power graph of a finite group is perfect. So a natural question is:

For which finite groups G is the commuting graph perfect?

For example, for the alternating group A5, the commuting graph consists of a bunch of complete graphs with one vertex from each complete graph identified; it is clearly perfect. However, the commuting graph of S5 is not perfect, since the five transpositions (1,2), (2,3), (3,4), (4,5), and (5,1) induce a cyclic subgraph.

I did wonder if perhaps the commuting graph of a soluble group might be perfect; but this is false. The group with presentation

a0,…,a4 | ai2=(aiai+1)2=(aiai+2)4=1 (i=0,…,4)⟩

(indices mod 5) is presumably infinite, but it has finite quotients in which the orders of elements are precisely as specified: for example, its largest nilpotent quotient of class 2 has order 1024. The five images of the generators in this quotient induce a 5-cycle.

This can be generalised. Given a graph X, the graph group FX is the group generated by elements av for vertices v of X, with relations asserting that generators corresponding to adjacent vertices commute. Let us say that a homomorphic image of a graph group is large if the images of the generators are all distinct and not the identity, and the images of generators corresponding to non-adjacent vertices do not commute. Then any finite large quotient of a graph group FX, where X is an odd cycle of length at least 5 or the complement of one, has imperfect commuting graph. Conversely, by the Strong Perfect Graph Theorem, the commuting graph of a group G is imperfect if and only if G contains a subgroup which is a large quotient of such a graph group.

This characterisation is not very helpful – but at least it suggests that progress on this problem depends on describing large finite quotients of these specific graph groups.

Advertisements

About Peter Cameron

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

3 Responses to Perfectness of commuting graphs

  1. Nick Gill says:

    Peter, I came across this post after asking (and answering) the following related question on mathoverflow: http://mathoverflow.net/questions/110404/when-does-a-distinguished-matching-exist

    With regard to the perfectness of commuting graphs, I believe Brown has written two papers concerned with the symmetric groups that prove that the chromatic and clique numbers of the NON-commuting graph do not coincide for n>=15. Which implies that these non-commuting graphs are not perfect and hence, by the WPGT, that the corresponding commuting graphs are not perfect either.

    Azad, Britnell and I have some (currently unpublished) results for simple groups of Lie type and for GL_n(q) which may (eventually) yield an answer to which of these groups have perfect commuting graph.

    Best wishes, Nick Gill

  2. Dear Peter,

    Nick and I have figured out the quasisimple groups with perfect commuting graphs. There are two infinite families — SL_2(q) and Sz(q) — and 15 others, of which the only simple groups are
    A_6, L_3(2) and L_3(4).

    We also give very restrictive conditions on the components (subnormal quasisimple subgroups) of a group G with perfect commuting graph. Amongst other things, we show that G can have no more than two components.

    Our results can be found at arXiv:1309.2237.

    Best wishes,
    John Britnell

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s