Ramsey Number

Overview

Ramsey numbers measure when a large enough system must contain a homogeneous pattern. In the graph formulation every pair receives one of two colors, and the goal is a prescribed monochromatic clique. The forcing statement concerns every coloring; a single counterexample coloring proves that a proposed size is still too small.

Prerequisites

Know complete graphs, cliques, edge colorings, and the pigeonhole principle. A clique of size $s$ means $s$ vertices with all $\binom s2$ connecting edges present. Colors label edges, rather than vertices.

Definition and conventions

For positive integers $s,t$, define $R(s,t)$ as the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$.

The word “or” is inclusive: both may occur. Monochromatic cliques need not be maximal. A single vertex counts as a monochromatic $K_1$ in either color because it has no edges to check. Consequently $R(1,t)=R(s,1)=1$, while $R(2,t)=t$. The finite Ramsey theorem guarantees existence for these parameters.

Intuition

The coloring tries to conceal uniform groups. Adding vertices creates more opportunities, but density in one color alone does not settle every parameter. The universal quantifier explains why upper bounds and lower bounds use different arguments: an upper bound must handle all colorings, while a lower bound needs one avoiding both targets.

Examples and non-examples

For $R(3,3)$, take any vertex in $K_6$. At least three of its five incident edges have the same color, say red. Among their three other endpoints, a red edge completes a red triangle with the chosen vertex. If no such edge exists, those three endpoints form a blue triangle. Thus $R(3,3)\le6$.

To prove the reverse inequality, color the edges of a five-cycle inside $K_5$ red and its remaining edges blue. The red graph is a five-cycle, and the blue graph is also a five-cycle. Neither contains a triangle. Hence $R(3,3)>5$, so it equals six.

An arbitrary coloring of an incomplete six-vertex graph need not contain either triangle. The complete host is a hypothesis, not a cosmetic choice.

Important properties

Swapping colors proves $R(s,t)=R(t,s)$. Increasing either target size cannot decrease the Ramsey number.

For $s,t\ge2$, the recurrence

also proves finiteness inductively. At a chosen vertex in a host of that size, either the red neighborhood has at least $R(s-1,t)$ vertices or the blue neighborhood has at least $R(s,t-1)$. Otherwise the two neighborhoods together would have at most two fewer than the host size, although they contain all remaining vertices. Apply the smaller Ramsey statement within the appropriate neighborhood, then append the chosen vertex when needed.

Connections and further reading

Probabilistic methods produce colorings avoiding larger monochromatic cliques. Extremal graph theory studies each color class through its forbidden subgraphs. Morris, §14.2, Definition 14.2.2 and Proposition 14.2.4 supports the finite two-color formulation. This entry states classical facts and makes no claim about the latest unresolved numerical bounds.