This post contains brief descriptions of some mathematics that one would need to know in order to have a realistic chance of contributing to the collaborative research project I shall suggest in the next post. If you are familiar with the Hales-Jewett theorem, Szemerédi’s regularity lemma, the triangle-removal lemma, and the proof from the triangle-removal lemma that a dense subset of contains a corner, then you do not need to read it.
The Hales-Jewett theorem.
The Hales-Jewett theorem is one of the best-known results in Ramsey theory. To state it, we need a couple of definitions. Let us write for the set . We shall be looking at colourings of the set which consists of all sequences , where each is an integer between and .
As with most Ramsey theorems, the idea is now to find a substructure with all elements of the same colour. In this case, the substructure is an object known as a combinatorial line. An example will quickly demonstrate what a combinatorial line is. Let and let . Then the following three points form a combinatorial line: To see more clearly what is going on here, let us use the notation . The three earlier points are obtained by substituting , then , and then . In general, you form a combinatorial line by fixing some of the coordinates and letting the others be equal and vary from to .
The Hales-Jewett theorem asserts that for every and every there exists such that if the elements of are coloured with colours, then there is a combinatorial line with all its points of the same colour.
The Furstenberg-Katznelson theorem.
The proof of the Hales-Jewett theorem need not concern us here. What we shall be interested in is the density version of the statement, which is the following. For every and every there exists such that every subset of of size at least contains a combinatorial line. This is a famous theorem of Furstenberg and Katznelson, who proved it using ergodic theory. As yet, the only known proofs of this theorem either use ergodic theory or are heavily inspired by it, so it would be very nice to have a purely combinatorial proof.
The Hales-Jewett theorem implies van der Waerden’s theorem, and the Furstenberg-Katznelson theorem implies Szemerédi’s theorem, so a new proof of any kind is not likely to be easy to come by. However, Szemerédi’s theorem for progressions of length 3 (due to Roth) is quite a bit easier than the general case, so there ought to be a better chance of finding a combinatorial proof of the Furstenberg-Katznelson theorem at least in the case . The project I’m proposing is to develop an approach to this case of the problem: the approach will be explained in the next post. (If you have an idea about how to find a proof of this case, you should save it up for comments on that post. I’m not expecting many comments on this post, but if you do have them then they should concern the results I briefly describe here, or my presentation of them.)
Szemerédi’s regularity lemma.
The second piece of background information needed is Szemerédi’s regularity lemma. This is a fundamental result in graph theory and will play an important role for us. I will give the statement only, even though the project may depend on thinking about, and trying to modify, its proof. Anybody who does not know the proof already is referred to section 7 of this paper, and also to section 1 and the beginnings of sections 2 and 3 (but you can ignore everything about hypergraphs).
In order to state the lemma we shall need some preliminary definitions. Let be a bipartite graph with vertex sets and . Let be a subset of and let be a subset of . The density of the pair is defined to be the number of such that is an edge of , divided by . The pair is defined to be -regular if whenever and are subsets of and with and . What is useful about -regular pairs is that the induced subgraph of corresponding to such a pair behaves rather like a typical random bipartite graph of the same density (at least when is small).
The statement of the lemma, in the version we shall use, is this. For every there exists such that for every graph with vertex set there is a partition with and with the sets differing in size by at most 1, such that all but at most of the pairs are -regular.
As most people think about this lemma: every graph can be partitioned into a bounded number of pieces, almost all of which behave like random bipartite graphs.
The triangle-removal lemma.
Now let me sketch how Szemerédi’s regularity lemma is used to prove a result that is slightly misleadingly called the triangle-removal lemma. This states that for every there exists such that if is any graph with vertices and at most triangles, then it is possible to remove at most edges from and end up with no triangles. To prove it, one first applies the regularity lemma to . Let be a fairly small number (that depends in a reasonably simple way on ) and let the partition of the vertex set given by the regularity lemma be . Then remove all edges from all pairs that either fail to be -regular or fail to have density at least . If has been chosen appropriately, the number of edges removed is at most Suppose now that the graph with these edges removed had a triangle . Suppose that , and . Then the pairs , and would not have had their edges removed, so they would have had to be both -regular and of density at least . If is sufficiently small, it is not hard to deduce from these two properties that the number of (labelled) triangles with one vertex in , one in and one in is not much smaller than . Since each cell of the partition contains a constant fraction of all the vertices, this gives us a lot of triangles, contradicting the assumption that there were fewer than triangles, at least if is chosen small enough.
Finding corners in dense sets.
Now let us use the triangle-removal lemma to prove that a dense subset of contains a triple of the form with . Such a configuration is sometimes called a corner. Suppose then that is a set of size . Form a tripartite graph with vertex sets and , and the following edges. If and , then is an edge if and only if . If and , then is an edge if and only if . Finally, if and , then is an edge if and only if .
Suppose now that is a triangle in this graph . Then the points , , and all belong to . Setting we can write the second and third points as and . Therefore, we have a configuration of the desired kind—except if . If , which happens if , then all we get is a single point repeated three times. Let us call the resulting triangle in the graph degenerate.
At any rate, if contains no configurations of the desired kind, then the above argument shows that contains no non-degenerate triangles. Since the number of degenerate triangles is , this proves that contains triangles, which is far fewer than triangles. (Recall that the number of vertices of is .)
The triangle-removal lemma therefore implies, at least when is sufficiently large, that it is possible to remove at most edges from in such a way that no triangles remain. However, this is a contradiction, as it is easy to check that no two degenerate triangles share an edge, and we know that there are of them.
The above very beautiful argument is due to Solymosi, who was generalizing a similarly beautiful argument of Ruzsa and Szemerédi. This result about corners was first proved (I think — but am ready to be corrected if necessary) by Szemerédi, using a different argument. [Actually it was Ajtai and Szemerédi: many thanks to Matthias Schacht for telling me this — which I now remember once having known.]
Sparse regularity lemmas.
This section assumes familiarity with the proof of Szemerédi’s regularity lemma. A drawback of Szemerédi’s regularity lemma is that the bound on the size of the partition in terms of the parameter is very weak. This means that in practice the lemma is useful only for statements about dense graphs. However, there do exist adaptations that work for sparse graphs (some of which are described in the first couple of sections of this paper). Roughly, the idea is that one can prove a regularity lemma for a sparse graph if it is a dense subgraph of a sufficiently random-like graph . And very roughly, the reason for that is that if has density and has highly quasirandom behaviour, then the upper bound for the density of subgraphs of is not but , which means that the mean-square density of a partition cannot be more than , so the iteration in the proof of the regularity lemma can after all be guaranteed to finish after a constant number of steps (since, if is dense in , the initial mean-square density is within a constant of ). An important difference between the sparse case and the dense case is that if you have a triple of bipartite graphs that are sparse and regular, it is no longer trivial that the resulting tripartite graph contains many triangles. However, there are various ways that this can be done.
What will happen next.
I don’t yet have a better place to do things than this blog, so here’s what I plan to do. Within the next day or two I will publish a (now written) post that explains a possible approach to the density Hales-Jewett theorem when . The project is to decide whether this approach works or (more likely) can be convincingly shown not to work. Or at least that is the initial project — it is possible that there could be spin-offs.
As well as the main post that describes the approach, I shall also publish an explanation (also already written) of why I think this project might be a suitable one, as well as a dozen or so subposts, some of which will be empty. The idea of these subposts is to compensate to some extent for the excessive linearity of blog comments by separating out discussion of different aspects of the project. However, I don’t want to dictate too much the form that the discussion should take, so I will also leave several of the subposts empty, and fill them if it becomes clear from the existing discussions that a new thread would be appropriate. (If this happens, I will fill the empty post with an attempted summary of the comments that have led to the new thread.) It’s a bit rough and ready, and won’t work if there are too many comments to deal with, but I’m hoping that the problem is at a level where the number will be manageable. The point of publishing empty posts is that then they will all appear consecutively on the blog.
Added later: I have slightly changed my mind about one detail. As planned, I shall publish a large number of extra posts for the purposes of trying to organize the threads of the discussion. However, I will not try to guess in advance what any of these threads might be, so initially all these extra posts will be empty. Only when clearly defined subdiscussions emerge will I suggest that they continue on separate threads. This is because I want the whole process to be as democratic as possible: ideally it won’t always be me who decides that a subdiscussion is sufficiently “clearly defined” to deserve its own place.
Tags: Polymath project