The enhanced power graph is weakly perfect

Earlier this year, I posed a combinatorial problem, a solution to which would imply that, for any finite group G, the enhanced power graph of G is weakly perfect, that is, has clique number equal to chromatic number.

Recall that the vertices of the graph are elements of G, two vertices joined if they generate a cyclic group. It is easy to see that any clique in this graph is contained in a cyclic subgroup, so the maximum size of a clique is the maximal order of an element of G. That the chromatic number of this graph takes the same value would follow if, for any natural number n, we could find subsets A₁,…,A_n such that the cardinality of A_i is φ(i) (Euler’s totient) and, if gcd(i,j) ≤ n then A_i and A_j are disjoint.

I spent more time than I care to remember trying various sophisticated ways to make this construction, and inflicted the problem on several other people too. But as readers of this blog will remember, an unnamed correspondent came up with a simple direct construction that can be described in a line or two and takes only a little longer to prove correct.

The correspondent turned out to be Veronica Phan, who tells me she is a medical student in Ho Chi Minh City who does mathematics as a hobby. I think there is a lesson here for us!

We wrote this up and the paper is now on the arXiv: https://arxiv.org/abs/2207.07156