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 A1,…,An such that the cardinality of Ai is φ(i) (Euler’s totient) and, if gcd(i,j) ≤ n then Ai and Aj 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:

About Peter Cameron

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

19 Responses to The enhanced power graph is weakly perfect

  1. Laurent Therond says:

    Truly remarkable!

    Regards, Laurent

  2. dsp says:

    I am uncertain if I should post this here, but given the story in the post, it is perhaps allowable. I believe I have a simple proof of another one of your conjectures: That there is no generalised quadrangle with parameters (s,t) with s finite and t infinite. It goes like this: Let L_1, L_2, \dots be an enumeration of the lines in the quadrangle. Now consider the topological space T:= L_1 \times L_2 \times \cdots with the product topology, with each L_i given the discrete topology. Since s is finite, this is homeomorphic to Cantor space. Now associate a point t(p) \in T with each point p in the quadrangle as follows: If p \in L_i, then the ith coordinate of t(p) is simply p. If p \notin L_i, then the ith coordinate of t(p) is the unique point on L_i that is collinear with p. Let Q be the set of all points of the form t(p).

    Claim: For each t(p), there is an open set O \subset T such that O contains at most s+1 points in Q.

    Proof of the claim: Assume wlog that p \in L_i, so the ith coordinate of t(p) is p. Choose an arbitrary j such that the jth coordinate q of t(p) is not p. Note that by definition p and q are collinear. Now simply take as O the open (in fact, clopen) set of points in T that agree with t(p) on its ith and jth coordinate. I claim that every point t(p') \in O \cap Q must correspond to a point p' of the quadrangle that lies on the line determined by p and q. Indeed, if it did not lie on that line, then it would be collinear to the two points p and q on that line, which contradicts the definition of a generalised quadrangle.

    Now it is easy to see by combining the claim with the Hausdorff property of T that Q is an infinite set of isolated points in T. But since the Cantor space contains no infinite set of isolated points, we have a contradiction.

    • I am not sure about the last claim. What about the set 1000…, 11000…, 111000…, etc.? Of course this is not closed, so you could fix things by showing that Q has to be closed, but I don’t at the moment see this.

      • dsp says:

        You’re right, the proof does fail badly at this point. My mistake. The approach however has at least one interesting consequence: It shows that if a generalised quadrangle with parameters (s,t), s finite and t infinite, exists, then it must contain an ovoid. Indeed, we have seen that if the set Q were closed, that would lead to a contradiction. Then we have:

        Claim: If a point (p_1,p_2,\dots) is contained in the closure of Q, but not in Q, then no two of its coordinates p_i can be collinear in the quadrangle.

        Proof: Assume, for sake of contradiction, that p_i \neq p_j were collinear. Consider the clopen set that consists of the points with p_i as their ith and p_j as their jth coordinate. By definition, every point in Q that lies in this set must be of the form t(p) for a point p in the quadrangle that is collinear with both p_i and p_j. But since p_i, p_j are collinear, this means that p must lie on the line determined by them, and this line contains only s+1 points. Hence we have an open set containing (p_1,p_2,\dots) that contains only finitely many points of Q, but that means that (p_1,p_2,\dots) must either itself lie in Q, or not belong to its closure (since their can be no infinite sequence in Q converging to (p_1,p_2,\dots)).

        But the claim implies that whenever L_k contains p_i, then p_k = p_i, since otherwise p_k and p_i would be distinct and collinear, both being contained in L_k. But this means that the p_i are a set of points such that each line contains precisely one p_i, i. e., an ovoid.

  3. Nice that you can salvage something. I thought as I read the first comment that it was a neat trick, too good to waste.
    Jacques Tits told me once that he had made this conjecture (before I did), but I haven’t located it in his writing. Does anybody know a reference?

    • dsp says:

      If I am permitted one more comment:

      I think I have a more or less simple proof of the nonexistence of nontrivial semifinite generalized quadrangles after all. The proof is again topological and has evolved out of my two previous comments here during the past week (although so much has changed that nothing of the original proof attempt remains).

      So let Q be a generalized quadrangle on the point set \mathcal{P} and line set \mathcal{L} with parameters (s,t) with s \geq 2 finite and t infinite. For a point x \in \mathcal{P}, we let x^\perp denote the set of points collinear with x, and write \mathcal{L}_x for the set of lines containing x. Now let T_\mathcal{P} be the topology on \mathcal{P} generated by the subbasis of all sets of the form \mathcal{P}_x := \mathcal{P} \setminus x^\perp for x \in \mathcal{P}, and let T_\mathcal{L} be the topology on \mathcal{L} generated by the subbasis consisting of all sets of the form \mathcal{L} \setminus \mathcal{L}_x for x \in \mathcal{P}.

      Claim 1: T_\mathcal{P} is Hausdorff.

      Proof: By the definition of a generalized quadrangle, for every line L := \{x_1,\dots,x_{s+1}\}, the distinct sets x_i^\perp all contain L, but partition the set \mathcal{P} \setminus L (indeed, if two such sets intersected in a point not on L, that point would be collinear with two distinct points on L — and if some point not on L were not contained in any such set, it would not be collinear with any point on L). But then it is fairly easy to see that x_i^\perp \setminus L = \bigcap_{j \neq i} (\mathcal{P} \setminus x_j^\perp) = \bigcap_{j \neq i} \mathcal{P}_{x_j} is open. Now since s \geq 2, for any two distinct points x,y, there must be a point distinct from x and collinear with x but not with y — indeed, if we take a line containing x but not y, then y is collinear with precisely one point on that line, which must contain a third point distinct from both x and the point collinear with y. So finally, given any two points x,y \in \mathcal{P}, we can choose a point x' collinear with x but not with y and a line L_{x'} containing x' but not x, and similarly a point y' collinear with y but not with x and a line L_{y'} containing y' but not y. And then x'^\perp \setminus L_{x'} and y'^\perp \setminus L_{y'} are disjoint open neighbourhoods of x and y, respectively.

      Claim 2: T_\mathcal{L} is Noetherian.

      Proof: We will prove this by showing that every subspace of T_\mathcal{L} is compact, which is after all equivalent to T_\mathcal{L} being Noetherian. By definition, the sets of the form \mathcal{L} \setminus \mathcal{L}_x form a subbasis of T_\mathcal{L}, so their intersections with a subset S \subseteq T_\mathcal{L} form a subbasis of S (with respect to the induced topology). By the Alexander subbase theorem, it therefore suffices to prove that if some sets of the form \mathcal{L} \setminus \mathcal{L}_x cover a subset S, then finitely many of them already cover it. But indeed, since two points in a generalized quadrangle determine at most one line and the number of points on that line s+1 is finite, the intersection of two distinct sets \mathcal{L}_x,\mathcal{L}_y is already finite, and by intersecting them with at most s+1 further sets of the form \mathcal{L}_z, we can reduce the intersection to \emptyset, which means that their complements cover S \subseteq T_\mathcal{L}.

      Now for the proof of nonexistence of Q with the stated parameters: Take an arbitrary point x \in \mathcal{P} and consider the space T_x := T_\mathcal{L} \setminus \mathcal{L}_x. Since subspaces of Noetherian spaces are Noetherian, it is Noetherian as well. Now consider the function f:T_x \longrightarrow T_\mathcal{P} that maps each line in T_x to its unique intersection with x^\perp. This function is continuous — indeed, one easily sees that the preimage f^{-1}(\mathcal{P}_y) of a subbasic open set \mathcal{P}_y is precisely the open set (\mathcal{L} \setminus \mathcal{L}_y) \cap T_x. Now since subspaces of Hausdorff spaces are Hausdorff and continuous images of Noetherian spaces are Noetherian, the image f(T_x) is both Hausdorff and Noetherian and therefore finite — which implies that x is collinear with finitely many points, contradicting the infinity of t.

      • dsp says:

        Actually, I made a small error in the presentation of the proof that T_\mathcal{L} is Noetherian: I confused points in T_\mathcal{L} (which correspond to lines in the quadrangle) with points in the quadrangle. The proof should go like this:

        Claim 2: T_\mathcal{L} is Noetherian.

        Proof: Again, we will prove this by showing that every subset of T_\mathcal{L} is compact. By the Alexander subbase theorem, it suffices to show that every cover of a subset S by sets of the form \mathcal{L} \setminus \mathcal{L}_x has a finite subcovering, since they form a subbasis of T_\mathcal{L} and therefore their intersections with S form a subbasis of S with respect to the induced topology. Case 1: The cover contains two sets \mathcal{L} \setminus \mathcal{L}_x, \mathcal{L} \setminus \mathcal{L}_y with x and y not collinear. Then these two sets already cover $\mathcal{L}$ (since there is no line containing both of x,y, and therefore the sets \mathcal{L}_x and \mathcal{L}_y do not intersect) and therefore also cover S. Case 2: All the x with \mathcal{L}_x are collinear, i. e., all the \mathcal{L}_x intersect in a line L of the quadrangle. Then L cannot be in S. But since any two sets $\mathcal{L}_x, \mathcal{L}_y$ intersect in at most one line, this again implies that any two sets \mathcal{L} \setminus \mathcal{L}_x, \mathcal{L} \setminus \mathcal{L}_y in the cover already cover $\mathcal{L} \setminus \{L\} \supset S$.

        Now everything works.

  4. dsp says:

    The last line of the proof should read: But since any two sets \mathcal{L}_x, \mathcal{L}_y intersect in at most one line, this again implies that any two sets \mathcal{L} \setminus \mathcal{L}_x, \mathcal{L} \setminus \mathcal{L}_y in the cover already cover \mathcal{L} \setminus \{L\} \supset S.

    • Interesting to watch a proof growing before my eyes! It reminds me of Graham Higman’s advanced classes in Oxford back in the day.
      I will try to read it this weekend. This is a public space, and any other readers are invited to read the proof and comment as well.

    • You’ll have to be patient, I’m afraid. I am not a topologist, and my undergraduate knowledge of topology does not extend to Noetherian topological spaces or the Alexander subbase theorem. Also I think the start of Case 2 is a bit garbled but I believe I can understand what you meant to say.

      • dsp says:

        I don’t know much about Noetherian topological spaces myself (this might increase suspicion of my claimed proof, but oh well), but I believe that this is at least somewhat due to the fact that nothing much of interest can be said about them: I believe they’re not really a central object of study of point-set topology and are mentioned only in passing in algebraic geometry texts, where they appear as spectra of Noetherian rings (hence their name). Correct me if I’m wrong about this.

        A topological space is called Noetherian iff every ascending sequence of open sets eventually stabilizes, i. e., for every infinite sequence of open sets O_1,O_2,\dots, there is an i such that O_j = O_i whenever j \geq i. That is the definition. Of course, it is equivalent to the dual definition that every descending sequence of closed sets eventually stabilizes.

        Note that if a space is Noetherian, then any coarser topology on the same set is Noetherian as well: If every sequence of open sets stabilizes and we remove some open sets, then every sequence of the remaining open sets will still stabilize, since it did so before the removal. Furthermore, it is easy to see that every subspace of a Noetherian space is also Noetherian: Indeed, if every sequence of open sets stabilizes, then so does the sequence of intersections of terms of that sequence with a fixed subset.

        As a result of the previous paragraph, we can show that a set X endowed with the topology T is Noetherian with respect to T by showing that there is a set X' \supset X and a Noetherian topology T' \supset T on X'. So I will give here another proof that the space T_\mathcal{L} in my proof is Noetherian by “embedding” it in this way (really, extending its groundset and its topology) in a topology well-known to be Noetherian: the Zariski topology on \mathbb{C}^{s+1} (this is Noetherian by the Hilbert Basis Theorem). This then dispenses with the Alexander Subbase Theorem and is perhaps also conceptually clearer. However, it requires the DeBruijn-Erdös theorem for hypergraphs (a hypergraph is strongly k-colorable with k finite iff all of its finite subgraphs are).

        First, I claim that the hypergraph whose vertices are the points of the quadrangle and whose edges are the lines, is strongly s+1-colorable. (In more “quadrangle-typical” terminology, the quadrangle can be partitioned into ovoids.) Indeed, the quadrangle must contain an infinite set of mutually disjoint lines. (There undoubtedly is a simple proof of this, but I can’t see it right now. In any case, this fact is in Cherlin’s paper on the problem.) So for every finite subset A \subset \mathcal{P}, there is a line disjoint from it, say, L := \{x_0,\dots,x_s\}. Now simply color a point in A with i iff x_i is the unique point on L that is collinear with it. This is a strong coloring of the lines contained in A, since no point on L can be collinear with two distinct collinear points not on L. Now by the DeBruijn-Erdös theorem, the whole hypergraph can be strongly s+1-colored, i. e., the quadrangle can be partitioned into ovoids \Omega_0,\dots,\Omega_s.

        Now for each i, let g_i : \Omega_i \longrightarrow \mathbb{C} be an arbitrarily chosen injective function, and for L = \{x_0,\dots,x_s\} \in \mathcal{L}, let g(L) := (g_0(x_0),\dots,g_s(x_s)) \in \mathbb{C}^{s+1}. Now, recalling that T_\mathcal{L} is generated by the subbasis consisting of sets of the form \mathcal{L} \setminus \mathcal{L}_x, all that remains to be shown is that each set \{g(L) \mid L \in \mathcal{L} \setminus \mathcal{L}_x\} is open in the topology on the image g(\mathcal{L}) induced from the Zariski topology on \mathbb{C}^{s+1}. But it is: Indeed, if x \in \Omega_i, then \{g(L) \mid L \in \mathcal{L}_x\} is the intersection of latex g(\mathcal{L})$ with the set of points in \mathbb{C}^{s+1} whose ith coordinate is g_i(x), which is a hyperplane and therefore Zariski-closed.

        Finally, a proof that the continuous image of every Noetherian space is Noetherian can be found at this page of the Stacks Project (Lemma 5.9.3).

        So this covers all the material on Noetherian spaces needed in the proof.

  5. dsp says:

    Sorry, Latex error. That sentence should read: „Indeed, if x \in \Omega_i, then the set \{g(L) \mid L \in \mathcal{L}_x\} is the intersection of g(\mathcal{L}) with the set of points in \mathbb{C}^{s+1} whose ith coordinate is g_i(x), which is a hyperplane and therefore Zariski-closed.“

    • dsp says:

      Also, I made two slight errors in the presentation of the DeBruijn-Erdös part: Of course a point on L can be collinear with two distinct collinear points not on L. But then the line determined by these points must intersect L and can therefore not be contained in A, since L was chosen disjoint from A.

      Also I wrote „subgraph“ at one point where I really meant „subhypergraph“.

      All this is not really of crucial importance, since I have already supplied a different proof that T_\mathcal{L} is Noetherian. But as I said, this one has the advantage of not needing the Alexander Subbase Theorem and is also nicely geometric: points in the quadrangle become hyperplanes, and the intersection of two such hyperplanes (if it intersects g(\mathcal{L})) contains a point corresponding to the line determined by them.

      • dsp says:

        Also (I should really proofread more carefully!) Noetherian means that every sequence O_1 \subseteq O_2 \subseteq \dots stabilizes. I forgot the inclusions. Again, a spelling mistake, not a gap in the proof.

  6. I’m afraid I hit a snag before I even got to claim 2. At the end of Claim 1 you find disjoint neighbourhoods of x and y. But if you take two nonadjacent points, say a and b, then the intersection of their perps is infinite (it contains one point on each line through a) and you can’t make this intersection empty by removing two (finite) lines.
    I agree that the topology is T_1, but I don’t see Hausdorff.

    • dsp says:

      You‘re right, I forgot the detail that the x‘ and y‘ in the proof must be chosen collinear, with L the line through them (so there will be no L_1 and L_2, only one L. Then the proof works: Their perps will be disjoint apart from L, and removing L will make the open sets disjoint. But we can always choose x‘ and y‘ to be collinear: after all, x but not y is collinear with x‘, and y must be collinear with a point y’ on every line containing x‘ — which x will then not be collinear with. So the proof of Hausdorffness works like this: We want to show that x and y have disjoint neighbourhoods. Take a point x‘ collinear with x but not with y and a line L containing x‘ but not x and let y‘ be the point on that line collinear with y. Then the perps of x‘ and y‘ will contain x and y, respectively, and removing L from them will make them disjoint. Does that make sense?

  7. dsp says:

    I’m afraid the comments in which I attempted to work around the Alexander Subbase Theorem by using the Zariski topology etc. contain a subtle error. It might be possible to fix it, but I think the cleanest way to prove that T_\mathcal{L} is Noetherian is by using the AST after all.

    • dsp says:

      Actually, come to think of it, there is a very simple way of showing that every subset of T_\mathcal{L} is compact without using the Alexander Subspace Theorem. (That a space is Noetherian if every subset is compact is, apart from being a known fact, easy to see: Indeed, if the space contained an ascending sequence of open sets O_1 \subset O_2 \subset \dots that does not stabilize, then the O_i would form a cover of \bigcup_{i = 1}^\infty O_i that has no finite subcover.) One simply uses the basic topological fact that a space is compact if every ultrafilter on it converges: So let X be a subset of T_\mathcal{L} and U a nonprincipal ultrafilter on X (the case of principal ultrafilters is trivial). It suffices to show that for some U contains every set of the form X \cap \mathcal{L} \setminus \mathcal{L}_x containing L for some L (since these sets form a subbasis). But now we simply observe that, since distinct sets of the form X \cap \mathcal{L}_x intersect in at most one element (since any two points in the quadrangle determine at most one line), U can contain at most one such set (since it is nonprincipal and can therefore not contain two sets intersecting in finitely many elements) — say, \mathcal{L}_y. Therefore it must contain all sets of the form X \cap \mathcal{L} \setminus \mathcal{L}_x containing L for each L \in \mathcal{L}_y.

Leave a Reply

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

You are commenting using your 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.