A sharp threshold for van der Waerden’s theorem in random subsets

A sharp threshold for van der Waerden’s theorem in random subsets, Discrete Analysis, 2016:7, 19 pp.

In recent years there has been a great deal of progress on problems that arise when one takes a notable combinatorial theorem such as Ramsey’s theorem or Szemerédi’s theorem and tries to prove that the same theorem holds in a very sparse random subset of the ground set. For example, if we apply this process to Ramsey’s theorem, then we find ourselves considering the following question. Say that a graph \(G\) satisfies the \(R(k,l)\)-property if for every 2-colouring of its vertices, either one colour class contains a clique with \(k\) vertices or the other colour class contains a clique with \(l\) vertices. How large does \(p\) have to be in order that a random graph with \(n\) vertices and edge-probability \(p\) has the \(R(k,l)\)-property with high probability?

Thanks to the work of several authors, there is now an established technology for solving such problems, in the sense that a bound for \(p\) can be found that is within a constant of best possible. This paper goes a step further and proves a sharp threshold for a sparse random version of van der Waerden’s theorem. Say that a subset \(A\subset\mathbb{Z}_n\) has the \(k\)-van der Waerden property if for any 2-colouring of its elements there is a monochromatic arithmetic progression of length \(k\). Then this paper proves that there is a function \(p(n)\) that lies between two constants \(c_1\) and \(c_2\) such that for every \(\epsilon>0\), if \(A\) has density less than \((1-\epsilon)p(n)n^{-1/(k-1)}\), then with probability tending to 1 (as \(n\) tends to infinity) it does not have the \(k\)-van der Waerden property, and if \(A\) has density greater than \((1+\epsilon)p(n)n^{-1/(k-1)}\), then with probability tending to 1 it does have the \(k\)-van der Waerden property. (The reason the threshold occurs at around \(n^{-1/(k-1)}\) is that that is the density at which the number of arithmetic progressions in the set starts to exceed the number of points.)

As is the case with many proofs of this kind, the authors do not determine the function \(p(n)\), or even prove that it converges, which is what one would of course expect. Instead, they use a general principle of Friedgut and Bourgain that says, roughly speaking, that a property has a sharp threshold as long as it is not “local”. To give an example, the graph property of containing a triangle is local, because it can be certified if you look at just three edges. By contrast, a small number of edges does not seem to be sufficient to certify that a graph has the \(R(k,l)\)-Ramsey property, so that property has a more “global” feel to it, so one would expect a sharp threshold.

The conditions of Friedgut and Bourgain are not easy to verify for Ramsey properties, so very few such results are known. (One example is that there is a sharp threshold for the \(R(3,3)\)-property.) This paper makes crucial use of a tool that has been developed only recently: the hypergraph container method of Balogh, Morris and Samotij, and of Saxton and Thomason. It represents a new state of the art in the area of sparse Ramsey theorems.