Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 1 / 17F (Graph Theory)

The diagonal diagonal Ramsey number $R(s)$ is the least $n$ such that every red-blue edge coloring of $K_n$ contains a monochromatic $K_s$. More generally let $R(s,t)$ require a red $K_s$ or blue $K_t$. The base cases are $R(1,t)=R(s,1)=1$. Given $R(s-1,t)+R(s,t-1)$ vertices, select one vertex. Either it has at least $R(s-1,t)$ red neighbors or at least $R(s,t-1)$ blue neighbors. Applying the corresponding smaller problem and, when needed, adjoining that selected vertex givesInduction and Pascal's identity now prove existence and

A graph $G$ with $v$ vertices is a subgraph of $K_v$. A monochromatic $K_v$ therefore contains a monochromatic copy of $G$; the copy need not be induced. Thus the preceding finite Ramsey theorem gives

At any vertex of $K_{2s}$ there are $2s-1$ incident edges. The pigeonhole principle ensures at least $s$ of one color. Those edges and their other endpoints form a monochromatic star $K_{1,s}$, regardless of the colors between the endpoints. Hence $R(K_{1,s})\le 2s$.

For odd $s$, place $2s-1$ vertices cyclically. Color red the edges of cyclic differences $\pm 1,\dots ,\pm (s-1)/2$, and blue every other edge. Each red degree is $s-1$, and each blue degree is also $(2s-2)-(s-1)=s-1$. There is no monochromatic $K_{1,s}$. For $s=1$ the same lower bound is the single-vertex graph. Together with the previous upper bound, this proves

For even $s$, suppose $K_{2s-1}$ had no monochromatic star with $s$ leaves. Both color degrees would be at most $s-1$ and their sum is $2s-2$, so both must equal $s-1$. The red graph would have odd degree at every one of an odd number of vertices, contradicting the handshaking lemma. Thus $2s-1$ vertices suffice.

On $2s-2$ vertices, split the vertices into two sets of size $s-1$, coloring inside each set red and across the sets blue. Red degrees are $s-2$ and blue degrees are $s-1$, so this avoids the star. Therefore