Journal of Combinatorics

Volume 2 (2011)

Number 4

An additive version of Ramsey’s theorem

Pages: 593 – 613

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n4.a7

Author

Andy Parrish (University of California at San Diego)

Abstract

We show that, for every $r, k$, there is an $n = n(r,k)$ so that any$r$-coloring of the edges of the complete graph on $[n]$will yield a monochromatic complete subgraph on vertices$\{ a + \sum_{i \in I} d_i \mid I \subseteq[k]\}$for some choice of $a, d_1, \ldots, d_k$.In particular, there is always a solution to$x_1 + \cdots+ x_\ell= y_1 + \cdots+ y_\ell$whose induced subgraph is monochromatic.

Full Text (PDF format)