In this post I want to discuss a combinatorial problem that is very appealing in its own right, but also important as a potential first step towards solving a central open problem in Ramsey theory. It is the second in a series of three posts (I may add to this number later, but three is what I have written or semi-written so far) that give further details about possible Polymath projects. This one was number 2 in the post in which I first discussed these projects. In that post, I said nothing beyond the fact that the project had close connections with the density Hales-Jewett theorem. Unlike the origin-of-life suggestion, this project is a straightforward mathematical one.
Let me very briefly indicate what the central open problem in Ramsey theory is. The density Hales-Jewett theorem, which has been discussed at great length on this blog, is the assertion that every dense subset of contains a combinatorial line (provided that is large enough in terms of and the density). This implies Szemerédi’s theorem.
Now there is an amazing generalization of Szemerédi’s theorem, due to Bergelson and Leibman, known as the polynomial Szemerédi’s theorem. This is the following assertion. For any and any choice of polynomials with integer coefficients and constant terms equal to zero, there exists such that every subset of size at least contains a subset of the form with . To see that this generalizes Szemerédi’s theorem, just let (unless you feel that is more natural).
Another special case of this theorem is when and . Then one is trying to find a subset of the form , or in other words a pair of elements of that differ by a perfect square. This was proved independently by Sarkozy and Furstenberg, though my favourite proof is a more recent argument due to Ben Green that follows more closely the general structure of Roth’s proof of Roth’s theorem.
An obvious question now arises: is there a generalization of DHJ that implies both DHJ and the polynomial Szemerédi’s theorem? So far, the answer is no, and that is the central problem I was referring to earlier. However, we do at least know the colouring version: that is, there is a colouring statement that simultaneously generalizes the Hales-Jewett theorem and van der Waerden’s theorem. This is a result of Bergelson and McCutcheon — alternative proofs have been given by Mark Walters (who has the shortest and simplest argument) and Saharon Shelah (who has produced a primitive recursive bound).
A result of this work is that we know what the correct statement of polynomial DHJ ought to be. It is slightly complicated, so first let me give one special case that is already enough to convey the flavour of it.
Conjecture 1. For every and every positive integer there exists such that if is any subset of of density at least , then contains a combinatorial line such that the wildcard set is of the form for some subset .
By considering the map that takes each element of to the sum of all its values, we find that the conjecture above implies the following special case of the polynomial Szemerédi theorem.
Theorem 2. For every and every there exists such that every subset of of density at least contains an arithmetic progression of length whose common difference is a perfect square.
The deduction is not quite trivial, but it is not too hard either. The main reason it holds is that the cardinality of is a perfect square.
Here is (one version of) the full polynomial density Hales-Jewett conjecture. It is a bit like a set-theoretic equivalent of trying to find and such that belongs to a given set whenever for every , just as Conjecture 1 resembles Theorem 2.
Conjecture 3. For every and every pair of positive integers and there exists such that if is any subset of of density at least , then contains a -dimensional combinatorial subspace such that the wildcard sets are of the form for some subset (where is understood to be a subset of the that appears in the product).
As far as I am aware, the polynomial version of DHJ is the only interesting statement of the form “Does every dense subset of such and such a structure contain a substructure of such and such a type?” where the answer is not known, even if one asks nothing at all about bounds. (I’m not saying that there are definitely no other interesting purely qualitative unsolved density conjectures, but I can’t think of any. I’d be interested to hear of others.)
One might expect Conjecture 1 to become hard when , but it is in fact not known even when . On reflection, this is not quite so surprising, since it implies the theorem of Sarkozy and Furstenberg, which is far from trivial. On the other hand, the theorem of Sarkozy and Furstenberg is significantly easier than the full polynomial Szemerédi theorem, so perhaps there is some hope of tackling the case of Conjecture 1.
A small variant of this case is particularly appealing combinatorially, and is what I would actually suggest as a good Polymath project.
Conjecture 4. For every there exists such that if is any collection of at least graphs with vertex set , then contains two distinct graphs and such that and is a clique.
From this conjecture one can deduce the special case of the polynomial Szemerédi theorem where one is looking for a pair of numbers of the form . (The polynomial does not have integer coefficients, but that is a minor technicality.) Bergelson and Leibman proved their theorem by first proving the colouring version (the polynomial van der Waerden theorem) and then using general ergodic machinery to deduce the density version. The colouring version followed by a sophisticated induction scheme (which they called PET induction), and in that scheme the polynomial was “easier” than the polynomial . Thus, there are two reasons for looking at this question about dense sets of graphs: it has a nice combinatorial formulation that does not require one to understand the terminology connected with the Hales-Jewett theorem, and it ought to be (trivially equivalent to) the easiest unsolved case of polynomial DHJ.
Here is a looser way of stating the conjecture: a dense set of graphs must contain two that differ by a clique. How might one go about proving this?
Here is an approach that doesn’t work, but it is still worth thinking about it in order to get a reasonable understanding of the difficulties of the problem. We can think of Conjecture 4 as a strengthening of Sperner’s theorem: we can reformulate Sperner’s theorem as the assertion that if you have a dense set of graphs, then you can find distinct graphs and in your set such that , and Conjecture 3 adds the requirement that should be a clique. (Of course, if we do not add some such requirement then the resulting statement is not really a statement about graphs at all.)
The “correct” proof of Sperner’s theorem, if we pretend that it is a statement about graphs, proceeds by considering a random ordering of all the edges of the complete graph on vertices. If is a dense set of graphs, and if we start with the empty graph and build up to the complete graph by adding random edges one at a time, then the expected number of times we produce a graph in is equal to times the equal-slices density of (which can be defined as the probability that a graph belongs if you first choose an integer uniformly at random from the set and then choose with edges uniformly at random from all such graphs). It is easy to show that if is dense, then it has equal-slices density greater than , and this completes the proof of Sperner’s theorem.
Can we adapt this idea to prove a properly graph-theoretic version of Sperner’s theorem? If we could find a way of randomly building up a sequence of graphs that started with the empty graph and ended with the complete graph and had the property that any two graphs in the sequence differed by a clique, then we would be in business. However, a moment’s thought shows that that is not even close to being possible: indeed, a union of two cliques cannot be a clique, so even a very short sequence of such graphs does not exist.
But it is not necessary to construct a sequence with such a ridiculously strong property. For example, suppose that one could build a sequence of graphs (where ) such that has edges, and is a clique whenever for some (which is clearly a necessary condition). That wouldn’t immediately lead to a proof, but it would be quite encouraging, because if ever intersected such a sequence densely, then by the polynomial Szemerédi theorem (in fact, this case follows also from the work of Sarkozy and Furstenberg) it would have to contain two graphs that differed by a clique.
Even this property is far too strong, however. For instance, it would require to be a triangle for every , and it doesn’t take long to convince oneself that that is impossible.
Nevertheless, these discouraging observations do not completely rule out covering almost all graphs by sequences that are sufficiently rich in clique differences for it to be possible to reduce the problem to a problem about sets of integers. One possible line of enquiry would be to see whether all such proofs can be ruled out. For example, perhaps it is the case that for every chain of graphs one can find a set of at least graphs in the chain such that no two differ by a clique. That would completely kill off all hopes of a Sperner-type proof, and it is also quite a nice problem in itself (though it may turn out to be easy).
Let me state that formally as a problem. It strikes me as an almost compulsory question to try to answer if one wishes to prove Conjecture 4.
Problem 5. Is it true that for every there exists a sequence of distinct graphs such that for every subset of size at least there exist such that and is a clique?
I suspect that this question is not too hard. In fact, I think Mark Walters probably already knows the answer. (No logical relationship is intended between those two sentences.) If the answer is yes, then one could set about trying to decompose the set of all graphs on vertices into a union of such sequences (or do something more general like approximating the uniform measure on the set of all graphs by a weighted sum of such sequences). However, I think it will be more interesting if the answer is no. Then one would be faced with the following question: what could a proof of Conjecture 4 conceivably look like?
One difficulty we would face with this problem if we adopted it as a Polymath project is that we do not have as wide a variety of model proofs to work with as we had with DHJ. The obvious theorem to try to generalize is the theorem of Sarkozy and Furstenberg, but the only two proof techniques that have so far given proofs of that theorem are Fourier analytic techniques (used by Sarkozy, and also in subsequent proofs such as that of Green) and ergodic techniques. It seems to be hard to develop an analogue of Fourier analysis in a Hales-Jewett setting—we had a try at that with DHJ(3), and although we did have some ideas we did not manage to use them to prove DHJ(3) itself. Having said that, we did find a Fourier-ish proof of Sperner’s theorem, so perhaps it would be worth revisiting those ideas.
An alternative approach might be to try to find a more combinatorial proof of the theorem of Sarkozy and Furstenberg. Given the way that the PET induction scheme works, it might be sensible to assume Szemerédi’s theorem. If we could find a density increment argument that made use of Szemerédi’s theorem, then we might be able to generalize it in a way that was similar to the way the modified version of Ajtai and Szemerédi’s proof of the corners theorem was generalized to yield DHJ(3). That is quite a long shot, but it still seems worth asking the following question.
Problem 6. Is there a combinatorial proof, using Szemerédi’s theorem as a black box, that shows that if is a dense subset of that contains no pair , then there is an arithmetic progression with length tending to infinity such that the density of inside is at least ?
How might Szemerédi’s theorem be useful, even in principle? I’m not sure, but the kind of thing I vaguely imagine is, say, a clever trick that associates a two-dimensional set with , finds a density increment in some set , where is an arithmetic progression and is a translate of , and does something clever with the diagonals.
That’s probably so vague as to be useless. One might get something better by examining the colour-focusing argument of Walters. It is admittedly a colouring argument, but it would at least give some ideas if we wanted a proof of the following kind (which is the basic form of the DHJ proof).
Step 1: Find a configuration of a certain kind in which is dense.
Step 2: Argue that many numbers cannot be in as a result, and that these numbers form a set with a certain structure to it. (This is where a close examination of Walters’s argument might give us some clues.)
Step 3: By averaging, show that has a density increment on a structured set.
Step 4: Show that a structured set can be almost entirely partitioned into arithmetic progressions with square common difference. (It’s plausible that Szemerédi’s theorem might be useful for this step.)
Step 5: By averaging, obtain a density increment on an arithmetic progression of square common difference.
Step 6: Iterate.
I am writing this section of the post after having been in contact with Mark Walters. It seems that part of what I wrote above may be wrong (in as far as a matter of judgment can be wrong). It turns out that he does not know the answer to Problem 5 above, and despite what I said above that is good evidence that the problem is after all hard. His instinct is that such a sequence of graphs does exist, and that if it didn’t exist then the entire theorem would be false.
That suggests another question one could think about.
Problem 7. Suppose that for every there is a dense set of graphs with vertex set such that no two differ by a clique. Does it follow that for every nested sequence there is a dense subset such that if then is not a clique?
In case that sounds a bit far fetched, let me indicate how one might go about proving it (not that I have any particular reason to suppose that this proof idea works). Given a nested sequence of graphs one would choose some that is much much bigger than and then cover the set of all graphs with vertex set as evenly as possible with “copies” of this sequence. Then one would take a dense set of graphs with vertex set and no clique difference, and by averaging one would find a copy of that contained at least elements of this dense set. This would show that the copy of had a dense subset with no clique difference, and hence that itself had a dense subset with no clique difference.
Since almost all graphs contain almost all small graphs as induced subgraphs, and do so with roughly the same frequency, it could be that the above sketch is basically correct, but I’d need to check. If it is, then Problem 5 is, as Mark thought, equivalent to the whole problem. In that case, attention would focus on the following question: how does one produce a nested sequence of graphs that is “rich” in clique differences?
To make that question very slightly more precise, let us define a class of graphs as follows. Given a nested sequence of , let be the graph with vertex set where is joined to if and only if is a clique. Let us call a graph constructed in this way a clique-difference graph. Problem 5 can be reformulated as follows.
Problem 5A. Is it true that for every there exists a clique-difference graph with vertices and independence number at most ?
(The independence number of a graph is the largest possible number of vertices you can find such that no two are joined, so this is equivalent to saying that you cannot find graphs in the corresponding nested sequence without two of them differing by a clique.)
Having reformulated Problem 5 in this way, we are in a position to ask weaker questions, and therefore to give ourselves some hope of getting started. For instance, one could ask the following general question.
Problem 8. What properties do clique-difference graphs have?
To give some idea of the kind of result one might hope for here, let me make the simple observation that clique-difference graphs are all triangle free, since a disjoint union of two cliques is never a clique. So we are searching for a triangle-free graph with small independence number (and hence large chromatic number). This might sound a bit worrying, but the difficulty already arises in the number-theoretic case. For instance, if you join two integers when they differ by a cube, you get a triangle-free graph (by a special case of Fermat’s last theorem, proved by Euler), but all dense sets of integers contain a difference equal to a cube (so there’s yet another solution to the nice problem of finding triangle-free graphs with arbitrarily large chromatic number).
Of course, the fact that clique-difference graphs are triangle free is working against us, but it may be that if we could understand the restrictions that clique-difference graphs have to satisfy, we would then be in a better position to work out whether clique-difference graphs with small independence number exist.
If constructing good clique-difference graphs seems to be too difficult, then another line of attack might be a probabilistic one. The following question encapsulates what I mean.
Problem 9. Let and define a nested sequence of graphs with vertex set by taking to have no edges and letting be the union of with a random edge not contained in . What can we say about the resulting clique-difference graph?
Looking at that after having written it, I’m not sure it’s such a great question. It looks to me as though if you add edges completely randomly, then there will be almost no clique differences in the resulting sequence. But perhaps one can do something more ingenious, such as adding edges in a way that favours vertices of high degree. (Such processes have been studied in detail as a way of modelling how the internet grows.) So let us interpret “random edge” above to mean “edge chosen according to some clever procedure that involves at least some randomization”. Even then, it is by no means clear that randomization will work better than a careful deterministic choice of graph sequence that creates many clique differences.