Imre Leader and Paul A. Russell

Our aim in this paper is to prove Deuber's conjecture on sparse partition regularity, that for every $m$, $p$ and $c$ there exists a subset of the natural numbers whose $( m, p, c )$-sets have high girth and chromatic number. More precisely, we show that for any $m$, $p$, $c$, $k$ and $g$ there is a subset $S$ of the natural numbers that is sufficiently rich in $( m, p, c )$-sets that whenever $S$ is $k$-coloured there is a monochromatic $( m, p, c )$-set, yet is so sparse that its $( m, p, c )$-sets do not form any cycles of length less than $g$.

Our main tools are some extensions of Ne\v{s}et\v{r}il-Rödl amalgamation and a Ramsey theorem of Bergelson, Hindman and Leader. As a sideline, we obtain a Ramsey theorem for products of trees that may be of independent interest.

2000 Mathematics Subject Classification: 05D10.

E-mail:
I.Leader@dpmms.cam.ac.uk
P.A.Russell@dpmms.cam.ac.uk