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

• Published in: Discrete analysis 2016-03
• Main Authors: Schacht, Mathias, Person, Yury, Hàn, Hiêp, Friedgut, Ehud
• Format: Article
• Language: English
• ISSN: 2397-3129; 2397-3129
• DOI: 10.19086/da.615

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