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 A_{5}, 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 S_{5} 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
⟨a_{0},…,a_{4} | a_{i}^{2}=(a_{i}a_{i+1})^{2}=(a_{i}a_{i+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 F_{X} is the group generated by elements a_{v} 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 F_{X}, 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.
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
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
Dear John,
Nice – thanks for the information!
Peter.