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*_{1},…,*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

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

Truly remarkable!

Regards, Laurent

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 be an enumeration of the lines in the quadrangle. Now consider the topological space with the product topology, with each given the discrete topology. Since s is finite, this is homeomorphic to Cantor space. Now associate a point with each point in the quadrangle as follows: If , then the th coordinate of is simply . If , then the th coordinate of is the unique point on that is collinear with . Let be the set of all points of the form .

Claim: For each , there is an open set such that contains at most points in .

Proof of the claim: Assume wlog that , so the th coordinate of is . Choose an arbitrary such that the th coordinate of is not . Note that by definition and are collinear. Now simply take as the open (in fact, clopen) set of points in that agree with on its th and th coordinate. I claim that every point must correspond to a point of the quadrangle that lies on the line determined by and . Indeed, if it did not lie on that line, then it would be collinear to the two points and 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 that is an infinite set of isolated points in . 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.

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 were closed, that would lead to a contradiction. Then we have:

Claim: If a point is contained in the closure of , but not in , then no two of its coordinates can be collinear in the quadrangle.

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

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

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?

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 be a generalized quadrangle on the point set and line set with parameters with finite and infinite. For a point , we let denote the set of points collinear with , and write for the set of lines containing . Now let be the topology on generated by the subbasis of all sets of the form for , and let be the topology on generated by the subbasis consisting of all sets of the form for .

Claim 1: is Hausdorff.

Proof: By the definition of a generalized quadrangle, for every line , the distinct sets all contain , but partition the set (indeed, if two such sets intersected in a point not on , that point would be collinear with two distinct points on — and if some point not on were not contained in any such set, it would not be collinear with any point on ). But then it is fairly easy to see that is open. Now since , for any two distinct points , there must be a point distinct from and collinear with but not with — indeed, if we take a line containing but not , then is collinear with precisely one point on that line, which must contain a third point distinct from both and the point collinear with . So finally, given any two points , we can choose a point collinear with but not with and a line containing but not , and similarly a point collinear with but not with and a line containing but not . And then and are disjoint open neighbourhoods of and , respectively.

Claim 2: is Noetherian.

Proof: We will prove this by showing that every subspace of is compact, which is after all equivalent to being Noetherian. By definition, the sets of the form form a subbasis of , so their intersections with a subset form a subbasis of (with respect to the induced topology). By the Alexander subbase theorem, it therefore suffices to prove that if some sets of the form cover a subset , 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 is finite, the intersection of two distinct sets is already finite, and by intersecting them with at most further sets of the form , we can reduce the intersection to , which means that their complements cover .

Now for the proof of nonexistence of with the stated parameters: Take an arbitrary point and consider the space . Since subspaces of Noetherian spaces are Noetherian, it is Noetherian as well. Now consider the function that maps each line in to its unique intersection with . This function is continuous — indeed, one easily sees that the preimage of a subbasic open set is precisely the open set . Now since subspaces of Hausdorff spaces are Hausdorff and continuous images of Noetherian spaces are Noetherian, the image is both Hausdorff and Noetherian and therefore finite — which implies that is collinear with finitely many points, contradicting the infinity of .

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

Claim 2: is Noetherian.

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

Now everything works.

The last line of the proof should read: But since any two sets intersect in at most one line, this again implies that any two sets in the cover already cover .

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.

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 , there is an such that whenever . 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 endowed with the topology is Noetherian with respect to by showing that there is a set and a Noetherian topology on . So I will give here another proof that the space 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 (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 -colorable with 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 -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 , there is a line disjoint from it, say, . Now simply color a point in with iff is the unique point on that is collinear with it. This is a strong coloring of the lines contained in , since no point on can be collinear with two distinct collinear points not on . Now by the DeBruijn-Erdös theorem, the whole hypergraph can be strongly -colored, i. e., the quadrangle can be partitioned into ovoids .

Now for each , let be an arbitrarily chosen injective function, and for , let . Now, recalling that is generated by the subbasis consisting of sets of the form , all that remains to be shown is that each set is open in the topology on the image induced from the Zariski topology on . But it is: Indeed, if , then latex g(\mathcal{L})$ with the set of points in whose th coordinate is , 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.

Sorry, Latex error. That sentence should read: „Indeed, if , then the set is the intersection of with the set of points in whose th coordinate is , which is a hyperplane and therefore Zariski-closed.“

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

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 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 ) contains a point corresponding to the line determined by them.

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

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.

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 and , 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?

Yes that works. So I can proceed to the next part…

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 is Noetherian is by using the AST after all.

Actually, come to think of it, there is a very simple way of showing that every subset of 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 that does not stabilize, then the would form a cover of 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 be a subset of and a nonprincipal ultrafilter on (the case of principal ultrafilters is trivial). It suffices to show that for some contains every set of the form containing for some (since these sets form a subbasis). But now we simply observe that, since distinct sets of the form intersect in at most one element (since any two points in the quadrangle determine at most one line), can contain at most one such set (since it is nonprincipal and can therefore not contain two sets intersecting in finitely many elements) — say, . Therefore it must contain all sets of the form containing for each .