Background to a Polymath project

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 \null [n]^2 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 \null [k] for the set \{1,2,\dots,k\}. We shall be looking at colourings of the set \null [k]^n, which consists of all sequences (x_1,\dots,x_n), where each x_i is an integer between 1 and k.

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 k=3 and let n=10. Then the following three points form a combinatorial line: (1,3,2,1,1,3,3,2,3,1), (2,3,2,1,2,3,3,2,3,2), (3,3,2,1,3,3,3,2,3,3). To see more clearly what is going on here, let us use the notation (*,3,2,1,*,3,3,2,3,*). The three earlier points are obtained by substituting *=1, then *=2, and then *=3. In general, you form a combinatorial line by fixing some of the coordinates and letting the others be equal and vary from 1 to k.

The Hales-Jewett theorem asserts that for every k and every r there exists n such that if the elements of \null [k]^n are coloured with r colours, then there is a combinatorial line with all its k 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 \delta>0 and every k there exists n such that every subset of \null [k]^n of size at least \delta k^n 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 k=3. 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 G be a bipartite graph with vertex sets X and Y. Let U be a subset of X and let V be a subset of Y. The density d(U,V) of the pair (U,V) is defined to be the number of (u,v)\in U\times V such that uv is an edge of G, divided by |U||V|. The pair (U,V) is defined to be \epsilon-regular if |d(U',V')-d(U,V)|\leq\epsilon whenever U' and V' are subsets of U and V with |U'|\geq\epsilon|U| and |V'|\geq\epsilon|V|. What is useful about \epsilon-regular pairs is that the induced subgraph of G corresponding to such a pair behaves rather like a typical random bipartite graph of the same density (at least when \epsilon is small).

The statement of the lemma, in the version we shall use, is this. For every \epsilon>0 there exists K such that for every graph G with vertex set X there is a partition X=X_1\cup\dots\cup X_k with k\leq K and with the sets X_i differing in size by at most 1, such that all but at most \epsilon k^2 of the pairs (X_i,X_j) are \epsilon-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 a>0 there exists c>0 such that if G is any graph with n vertices and at most cn^3 triangles, then it is possible to remove at most an^2 edges from G and end up with no triangles. To prove it, one first applies the regularity lemma to G. Let \epsilon>0 be a fairly small number (that depends in a reasonably simple way on a) and let the partition of the vertex set given by the regularity lemma be X_1\cup\dots\cup X_k. Then remove all edges from all pairs (X_i,X_j) that either fail to be \epsilon-regular or fail to have density at least a/2. If \epsilon has been chosen appropriately, the number of edges removed is at most an^2. Suppose now that the graph with these edges removed had a triangle xyz. Suppose that x\in X_i, y\in X_j and z\in X_k. Then the pairs (X_i,X_j), (X_i,X_k) and (X_j,X_k) would not have had their edges removed, so they would have had to be both \epsilon-regular and of density at least a/2. If \epsilon is sufficiently small, it is not hard to deduce from these two properties that the number of (labelled) triangles with one vertex in X_i, one in X_j and one in X_k is not much smaller than (a/2)^3|X_i||X_j||X_k|. 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 cn^3 triangles, at least if c is chosen small enough.

Finding corners in dense sets.

Now let us use the triangle-removal lemma to prove that a dense subset of \null [n]^2 contains a triple of the form (x,y), (x,y+d), (x+d,y) with d\ne 0. Such a configuration is sometimes called a corner. Suppose then that A\subset [n]^2 is a set of size \delta n^2. Form a tripartite graph G with vertex sets X=Y=[n] and Z=[2n], and the following edges. If x\in X and y\in Y, then xy is an edge if and only if (x,y)\in A. If x\in X and z\in Z, then xz is an edge if and only if (x,z-x)\in A. Finally, if y\in Y and z\in Z, then yz is an edge if and only if (z-y,y)\in A.

Suppose now that xyz is a triangle in this graph G. Then the points (x,y), (x,z-x), and (z-y,y) all belong to A. Setting d=z-x-y we can write the second and third points as (x,y+d) and (x+d,y). Therefore, we have a configuration of the desired kind—except if d=0. If d=0, which happens if x+y=z, 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 A contains no configurations of the desired kind, then the above argument shows that G contains no non-degenerate triangles. Since the number of degenerate triangles is \delta n^2, this proves that G contains \delta n^2 triangles, which is far fewer than n^3 triangles. (Recall that the number of vertices of G is 4n.)

The triangle-removal lemma therefore implies, at least when n is sufficiently large, that it is possible to remove at most \delta n^2/2 edges from G 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 \delta n^2 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 \epsilon 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 G if it is a dense subgraph of a sufficiently random-like graph H. And very roughly, the reason for that is that if H has density \delta and has highly quasirandom behaviour, then the upper bound for the density of subgraphs of G is not 1 but \delta, which means that the mean-square density of a partition cannot be more than \delta^2, 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 G is dense in H, the initial mean-square density is within a constant of \delta^2). 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 k=3. 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.

About these ads


18 Responses to “Background to a Polymath project”

  1. Pseudo-Polymath » Blog Archive » Friday Highlights Says:

    [...] scale math, a social [...]

  2. Terence Tao Says:

    Dear Tim,

    It might be useful to have a single category for all of the posts related to this project, as this would provide an easy way to view all such posts on a single web page. (In fact, should further work on the project also appear on other wordpress blogs, they can use the same category, so that they can be viewed in a single global wordpress location.)

  3. gowers Says:

    Terry, that’s an excellent idea and I can’t think why I didn’t think of it (especially as I was puzzling over how I could do what it does so easily).

    For some more interesting ideas, in response to some of which my plans have slightly changed, I recommend a look at Michael Nielsen’s response to the proposal.

  4. Michael Nielsen Says:

    Dear Terry and Tim,

    If the project is given a reasonably unique name, which is then used to tag posts, it should be easy to track across all blogging platforms, not just WordPress:

    A straight up Google search shows a lot of hits for “Polymath project”. But a Google blog search shows only a few blog hits, so maybe it’s a unique enough name already. If there’s a lot of activity on other blogs, perhaps Tim could add a link to the blog search on his blog, so other people are aware of this possibility?

  5. Jason Dyer Says:

    Doesn’t the delta in the Furstenberg-Katznelson theorem need to be also less than or equal to 1? Otherwise I’m interpreting something wrong.

    In the Quasirandomness, Counting and Regularity paper you link to, on page 32 line 3 Y_j should be |Y_j|.

  6. gowers Says:

    If \delta\geq 1 then the theorem as stated is trivially true … so \delta needs to be less than 1 for the statement to be interesting, but not for it to make sense.

  7. Mathematics, Science, and Blogs « Combinatorics and more Says:

    [...] a new approach to the “density Hales -Jewett theorem”. A background post apears here. Hillel Furstenberg and Izzy Katznelson’s proof of the density Hales-Jewett theorem was a [...]

  8. Michael Nielsen » The polymath project Says:

    [...] challenge is to find a purely combinatorial proof of the theorem. More background can be found here. Serious discussion of the problem starts [...]

  9. DHJ — the triangle-removal approach « Gowers’s Weblog Says:

    [...] lemma in Kneser graphs, vertex 10 is the normal triangle-removal lemma (as described in the background-information post), and we are looking for vertex 11. Since getting from 00 to 10 is by no means a triviality, [...]

  10. A quick review of the polymath project « What Is Research? Says:

    [...] and defined his goal as trying to get to a combinatorial solution for the problem. Gowers wrote a background post about the problem and a post about the procedure, where he incorporated feedback from Michael Nielsen and others. [...]

  11. A massively collaborative mathematical project « What’s new Says:

    [...] on the triangle removal lemma (see e.g. my Simons lecture on the subject, or Tim Gowers’ background article for the project), it is thus natural to ask whether the density Hales-Jewett theorem has a proof [...]

  12. Liveblogging Science 2.0 | Serendipity Says:

    [...] helps to make progress on the problem. (similar examples from other mathematicians, such as the polymath project), and a brand new blog for this: [...]

  13. D.H.J. Polymath « the Upper Story Idiot Says:

    [...] Mathematics Possible?” — he proposed an attack on a stubborn math problem called the Density Hales-Jewett Theorem. He encouraged the thousands of readers of his blog to jump in and start proving. Mathematics is a [...]

  14. Blogging, Tic Tac Toe and the Future of Math at Steven Landsburg | The Big Questions: Tackling the Problems of Philosophy with Ideas from Mathematics, Economics, and Physics Says:

    [...] an initial post asking “Is Massively Collaborative Mathematics Possible?”, he posted a description of the problem and invited his readers to have at it in [...]

  15. Michael Nielsen » Introduction to the Polymath Project and “Density Hales-Jewett and Moser Numbers” Says:

    [...] began the Polymath Project with a description of the problem to be attacked (see below), a list of rules of collaboration, and a list of 38 brief observations he’d made [...]

  16. Hyper-optimistic conjecture retrospective – Part 1 « Paul Delhanty Says:

    [...] that I’m the only person out there who thought that somewhat charmingly naive. Check out the brief descriptions of some mathematics that one would need to know in order to have a realistic chan… the DHJ Polymath project. Oh dear! With my fuzzy recollection of the the Pigeonhole principle and [...]

  17. The Promise — and Peril — of Open Science to Extension | Mission Extension: The Weblog Says:

    [...] The article highlights eminent mathematician and Cambridge University researcher Timothy Gowers’s efforts to solve a handful of highly complex mathematical problems by crowdsourcing them — inviting other people to weigh in with their own suggestions for resolving them.  He dubbed it the Polymath Project, an undertaking that ultimately produced a series of new ideas and insights as well as several collaborative papers published under the collective pseudonym DHJ Polymath. [...]

  18. Ciência e Colaboração | Facti Says:

    [...] quinze minutos após ele postar o problema no seu blog, um matemático húngaro-canadense publicou um comentário. Um professor americano de uma escola de [...]

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 1,416 other followers

%d bloggers like this: