Typical Ramsey properties of the primes, abelian groups and other discrete structures

Abstract

Given a matrix $A$ with integer entries, a subset $S$ of an abelian group and $r\in \mathbb{N}$, we say that $S$ is $(A,r)$-Rado if any $r$-colouring of $S$ yields a monochromatic solution to the system of equations $Ax=0$. A classical result of Rado characterises all those matrices $A$ such that $\mathbb{N}$ is $(A,r)$-Rado for all $r\in \mathbb{N}$. Rödl and Ruciński and Friedgut, Rödl and Schacht proved a random version of Rado's theorem where one considers a random subset of $[n]:=\{1,\dots ,n\}$ instead of $\mathbb{N}$. In this paper, we investigate the analogous random Ramsey problem in the more general setting of abelian groups. Given a sequence $(S_n{)}_{n\in \mathbb{N}}$ of finite subsets of abelian groups, let $S_{n,p}$ be a random subset of $S_n$ obtained by including each element of $S_n$ independently with probability $p$. We are interested in determining the probability threshold $\hat{p}:=\hat{p}(n)$ such that $$\underset{n\to \infty }{\lim }\mathbb{P}[S_{n,p}\text{ is }(A,r)\text{-Rado}]=\{\begin{array}{ll}0& \text{ if }p=o(\hat{p});\\ 1& \text{ if }p=\omega (\hat{p}).\end{array}$$ Our main result, which we coin the random Rado lemma, is a general black box to tackle problems of this type. Using this tool in conjunction with a series of supersaturation results, we determine the probability threshold for a number of different cases. A consequence of the Green-Tao theorem is the van der Waerden theorem for the primes: every finite colouring of the primes contains arbitrarily long monochromatic arithmetic progressions. Using our machinery, we obtain a random version of this result. We also prove a novel supersaturation result for $S_n:=[n{]}^d$ and use it to prove an integer lattice generalisation of the random version of Rado's theorem. Various threshold results for abelian groups are also given.

59 pages, 1 figure. Updated to include Theorem 4.4