Ramsey Theory Introduction

Ramsey theory's central phenomenon — unavoidable order in sufficiently large or dense systems — recurs across mathematics and beyond. In number theory, van der Waerden's theorem (any finite coloring of the integers contains monochromatic arithmetic progressions of every length) is a direct sibling of Ramsey's theorem, proved by similar pigeonhole-and-induction ideas. In geometry, the Erdős–Szekeres "Happy Ending" theorem uses Ramsey-type arguments to show that any sufficiently large set of points in general position contains a convex polygon of prescribed size. In theoretical computer science, Ramsey-type bounds appear in the analysis of communication complexity, property testing, and the design of algorithms that must find structured substructures (cliques, independent sets) inside large graphs; the extremal question "how large before structure is forced" underlies lower-bound arguments for randomized and deterministic algorithms alike. In logic and model theory, Ramsey's original motivation — decidability questions for restricted fragments of first-order logic — remains an active thread, and infinite Ramsey theory (colorings of infinite sets) connects directly to set-theoretic notions of large cardinals. In statistics and coding theory, Ramsey-flavored pigeonhole arguments underlie bounds on error-correcting codes and combinatorial designs, where one seeks configurations that avoid excessive local uniformity. Finally, the technique used to attack Ramsey numbers themselves — since exact values are so hard to pin down, one turns to randomized constructions and probabilistic estimates — is precisely the on-ramp to the probabilistic method, where Erdős's 1947 lower-bound argument for $R(s,s)$ via random colorings is the founding example of an entire modern toolkit in combinatorics.

Ask the tutor: How does the probabilistic method give a lower bound for $R(s,s)$ without ever exhibiting an explicit good coloring?

Think of $K_n$'s edges as being labeled by a referee who is actively trying to avoid creating any monochromatic triangle (or clique, in general). For small $n$, the referee has plenty of room to maneuver: with few vertices, there just aren't enough edges to force a repeated pattern. As $n$ grows, the referee has exponentially more colorings to choose from — $2^{\binom{n}{2}}$ of them — but the number of potential monochromatic cliques to avoid also grows, and combinatorially it grows faster. Ramsey's theorem says the referee eventually loses no matter what strategy is used: past a threshold $n = R(s,t)$, some monochromatic clique is unavoidable in every coloring. The picture to hold in mind is a complete graph on $n$ vertices with each edge given one of two colors, and the question "is there a monochromatic triangle?" For $n=5$ the referee can win — one explicit successful coloring is the graph in which one color class is a 5-cycle and the other color class is its complement (also a 5-cycle). For $n=6$, no matter how the referee colors, some triangle is forced to be monochromatic. The jump from "escapable" to "inescapable" happens at exactly $n=6$, which is why $R(3,3)=6$.

Example 1: Proving $R(3,3) = 6$ exactly. We must show two things: $R(3,3) \leq 6$ (every 2-coloring of $K_6$ has a monochromatic triangle) and $R(3,3) > 5$ (some 2-coloring of $K_5$ has no monochromatic triangle). Upper bound $R(3,3)\le 6$, direct pigeonhole proof (independent of the general recursion, for concreteness). Take any 2-coloring of $K_6$ and fix a vertex $v$. It has 5 incident edges, each red or blue. By the pigeonhole principle, at least $\lceil 5/2 \rceil = 3$ of them share a color; say (relabeling colors if needed) at least three edges $vu_1, vu_2, vu_3$ are red. Now examine the triangle $u_1 u_2 u_3$:

• If any one of its three edges, say $u_1u_2$, is red, then $v, u_1, u_2$ form a triangle with all edges red ($vu_1, vu_2$ red by choice, $u_1u_2$ red by assumption) — a red monochromatic triangle.
• If instead none of $u_1u_2, u_1u_3, u_2u_3$ is red, all three are blue, so $u_1,u_2,u_3$ form an all-blue triangle.

Either way a monochromatic triangle exists. Since $v$ and the coloring were arbitrary, every 2-coloring of $K_6$ contains a monochromatic triangle, so $R(3,3) \leq 6$. Lower bound $R(3,3) > 5$: an explicit good coloring of $K_5$. Label the vertices $0,1,2,3,4$ arranged in a cycle. Color an edge $\{i,j\}$ red if $|i-j| \equiv 1 \pmod 5$ (i.e. the edge lies on the 5-cycle $0$-$1$-$2$-$3$-$4$-$0$), and blue if $|i-j| \equiv 2 \pmod 5$ (the "pentagram" chords). This uses all $\binom{5}{2}=10$ edges: 5 cycle edges (red) and 5 chord edges (blue). Check there is no red triangle: the red graph is the 5-cycle $C_5$, which has no triangles at all (its shortest cycle has length 5). Check there is no blue triangle: the blue graph is also a 5-cycle (the chords $0$-$2$-$4$-$1$-$3$-$0$ form a second pentagon), again triangle-free. So this coloring of $K_5$ avoids monochromatic triangles entirely, proving $R(3,3) > 5$, i.e. $R(3,3) \geq 6$. Combining both bounds: $R(3,3) = 6$.

Example 2: A non-symmetric, "adversarial" coloring of $K_6$, verified by hand. To make the upper bound concrete and check it against an actual example (rather than a symmetric one), take $K_6$ on vertices $\{1,2,3,4,5,6\}$ with the following deliberately irregular coloring, chosen to look as "random" as possible:

(This accounts for all $\binom{6}{2} = 15$ edges: 7 red, 8 blue.) Apply the proof's method at vertex $1$. Its incident edges are: $\{1,2\}$ red, $\{1,3\}$ red, $\{1,4\}$ blue, $\{1,5\}$ blue, $\{1,6\}$ blue. So the blue-neighbors of vertex $1$ are $\{4,5,6\}$ — already three vertices sharing a color at $1$, satisfying the pigeonhole step with the blue class (size 3, the majority side). Now inspect the triangle on $\{4,5,6\}$: the edges are $\{4,5\}$ (blue), $\{4,6\}$ (red), $\{5,6\}$ (red). Since not all three of these are blue, we are in the sub-case where we look for a red edge among the blue-neighbor set instead — indeed $\{4,6\}$ and $\{5,6\}$ are both red. Consider the triangle $\{4,6\}$-$\{5,6\}$: these two red edges share vertex $6$, but that alone doesn't yet give a monochromatic triangle; we must instead directly recheck against the theorem's dichotomy. Redo the check carefully, exactly as the proof demands: among $\{4,5,6\}$, since not all edges are the "pigeonhole color" (blue), find an edge of the other color connecting two of them together with vertex $1$ forming red — but vertex $1$'s edges to $4,5,6$ are blue, not red, so we instead apply the correct branch: since $\{4,5,6\}$ is not a blue triangle (because $\{4,6\}$ is red), we look for whether the non-blue-colored edge already closes a red triangle elsewhere, OR — matching the proof's actual logic — a monochromatic triangle is guaranteed inside $\{4,5,6\} \cup \{1\}$ if some edge of $\{4,5,6\}$ is blue (giving blue triangle with vertex 1) or if all three edges of $\{4,5,6\}$ are red. Here neither occurs purely inside that triple ($\{4,5\}$ is blue but $\{4,6\},\{5,6\}$ are red — mixed), so this particular triple does not yet exhibit the guaranteed triangle; the proof's guarantee is that some triangle exists in $K_6$, not that it lies in this specific triple unless the pigeonhole majority is fully monochromatic amongst itself. Let's instead search $K_6$ directly and confirm a monochromatic triangle exists somewhere, as the theorem promises. Check triangle $\{1,2,4\}$: edges $\{1,2\}$ red, $\{2,4\}$ red, $\{1,4\}$ blue — mixed, not monochromatic. Check $\{2,4,6\}$: edges $\{2,4\}$ red, $\{4,6\}$ red, $\{2,6\}$ red. All three red. This is a monochromatic (red) triangle, exactly as Ramsey's theorem guarantees. This example illustrates two things at once: first, that the pigeonhole step in the proof only locates a candidate region (here, the blue-neighbors of vertex 1) which may or may not itself contain the triangle, since the true logical guarantee is a disjunction (blue triangle among the neighbors, or a red edge from the hub closing a red triangle) — and second, that regardless of which coloring one tries, hunting through the 15 edges of $K_6$ always turns up a monochromatic triangle, confirming $R(3,3) \le 6$ concretely rather than just abstractly.