Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A / 2

The Ramsey number $R(s,t)$ is the smallest integer $N$ such that every red-blue colouring of the edges of $K_N$ has a red $K_s$ or a blue $K_t$. Equivalently, every graph on $N$ vertices contains a clique of size $s$ or an independent set of size $t$.

Set $R(1,t)=R(s,1)=1$. For $s,t\ge 2$, let $N=R(s-1,t)+R(s,t-1)$ and fix a vertex $v$ in a red-blue colouring of $K_N$. Among the remaining $N-1$ vertices, either at least $R(s-1,t)$ are red neighbors of $v$, or at least $R(s,t-1)$ are blue neighbors. In the first case their induced colouring gives a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. This proves the Ramsey number recursionInduction on $s+t$, using the boundary values and Pascal's identity, now gives the binomial upper bound for a Ramsey number:In particular this induction proves that the required Ramsey number exists.

Colour the edge $ij$ of the complete graph on $\{1,\dots ,6\}$ by the class containing $|j-i|$. Part (a) gives $R(3,3)\le 6$, so there is a monochromatic triangle with vertices $i<j<k$. Its three edge differences areThey are positive integers in one class. Hence every two-colouring of the positive integers has a monochromatic solution of $x+y=z$. This is the two-colour Schur theorem. The two summands need not be distinct.

No. Colour the positive integers by alternating dyadic blocks:Every positive integer $x$ and its double $2x$ have opposite colours. A nonempty set closed under addition contains both $x$ and $x+x=2x$, so no such set can lie in one class. In particular there is no infinite monochromatic additive subsemigroup.

The suggested arithmetic-progression argument gives another way to see the obstruction. If $a\in S$ and $S$ is closed under addition, then $a,2a,3a,\dots$ all lie in $S$. But every infinite arithmetic progression of positive step $d$ meets every sufficiently long dyadic block, because a block of at least $d$ consecutive integers contains a representative of the progression's residue class. Both colours contain arbitrarily long blocks, so neither colour contains an infinite arithmetic progression.