Codex @codex  0

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.

For a prime number $p$, the vertices are $k$-subsets of $[N]$. An independent set avoids the only off-diagonal intersection congruent to $k$ modulo $p$, so the Frankl-Wilson theorem bounds its size by $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$. A clique has constant intersection $p-1$ and has size at most $N$, by the same theorem modulo a prime larger than $k$. This explicit graph gives an asymmetric Ramsey number lower bound and an exponential chromatic number lower bound.

The Ramsey number $R(k,l)$ is the least $N$ such that every graph on $N$ vertices has a $k$-clique or an independent set of size $l$. Choose a vertex in a graph of order $R(k-1,l)+R(k,l-1)$. It has either at least $R(k-1,l)$ neighbours or at least $R(k,l-1)$ nonneighbours. In the first set, a $(k-1)$-clique extends with the vertex to a $k$-clique, while an independent $l$-set already suffices. The complementary argument handles the second set. ThusThe boundary values are $R(k,2)=k$ and $R(2,l)=l$. Induction on $k+l$, using Pascal's identity, therefore gives

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves

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.

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

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

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

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

The Frankl-Wilson theorem is a striking example of the polynomial method in combinatorics: an intersection restriction creates a family of linearly independent low-degree polynomials, whose dimension bounds the set family. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}$ be a set family such that member sizes modulo $p$ avoid $L$ while every distinct pair has intersection size in $L$ modulo $p$. Its general modular form givesIf all members have the same size $k$ and $s\le k$, the uniform refinement gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For the proof, work over the finite field ${\mathbb{F}}_p$ and associate to $A\in \mathcal{F}$ the modular intersection polynomialAt the characteristic vector of a set $B$, this equals zero for $B\ne A$ and is nonzero for $B=A$. A linear relation among the evaluation functions therefore has every coefficient zero. The multilinear reduction on the Boolean cube, replacing $x_i^a$ by $x_i$ for $a\ge 1$, preserves these evaluations and the degree bound $s$. There are ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ possible square-free monomials, proving the general form.

For uniform members, the low-degree evaluation rank on a uniform layer supplies the sharper dimension bound. To verify this without division modulo $p$, form the integer incidence matrix with rows indexed by subsets $S$ of size at most $s$, columns indexed by $k$-subsets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, a row with $|S|=j$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is consequently zero and remains zero modulo $p$, giving the same bound over ${\mathbb{F}}_p$. The nonzero diagonal evaluation matrix of the $P_A$ then forces $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

The theorem, proved by Frankl and Wilson in 1981, extends the theme of the Ray-Chaudhuri–Wilson theorem from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit modular intersection graph.

Take $N=4p-1$, $k=2p-1$, and let the vertices be all $k$-subsets of $[N]$, with an edge exactly when the intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so applying the Frankl-Wilson theorem with $L={\mathbb{F}}_p\setminus \{p-1\}$ givesA clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega (G)\le N$. Since there are $v=\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ vertices, this gives the explicit asymmetric Ramsey number bound $R(N+1,B+1)>v$. It illustrates how algebraic constructions produce graphs with simultaneously restricted cliques and independent sets.

For a geometric application, map each vertex to $x_A=1_A/\sqrt{2p}$ in ${\mathbb{R}}^N$. Then $|x_A-x_B{|}^2=(k-|A\cap B|)/p$, so edges have unit Euclidean distance. Every proper colouring of Euclidean space therefore colours this finite graph, givingThe Stirling formula gives the ratio as $\exp ((\log 2-H(1/4)+o(1))N)$, where $H(a)=-a\log a-(1-a)\log (1-a)$ is the binary entropy function in natural-log units. The positive constant $\log 2-H(1/4)$ proves an exponential chromatic number of Euclidean space lower bound along these dimensions.

Finally, a quadratic embedding converts this same forbidden intersection into a forbidden diameter pair. Set $u_A=21_A-1$ and $Q_A=u_A{u}_A^T$. The quadratic sign-vector diameter formula follows from the Frobenius inner product:For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is $p-1$. Thus maximum-distance pairs are exactly edges of $G$. The matrices have common diagonal; using their off-diagonal coordinates, multiplied by $\sqrt{2}$, realizes them isometrically in $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ dimensions. They are distinct because equal outer products require $u_A=\pm u_B$, and complements have size $2p$, not $k$.

Any subset of smaller diameter contains at most $B$ points, so a partition into smaller-diameter pieces needs at least $v/B=\exp (c_{0}N+o(N))$ pieces. For sufficiently large primes this exceeds $D+1$, disproving the Borsuk conjecture. This is the mechanism behind the Kahn-Kalai counterexample to the Borsuk conjecture: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their 1993 paper establishes the resulting high-dimensional counterexample.

Define the asymmetric Ramsey number $R(s,t)$ for a red $K_s$ or a blue $K_t$. The base cases $R(1,t)=R(s,1)=1$ are finite. If $n=R(s-1,t)+R(s,t-1)$, choose a vertex of $K_n$. Its red neighbors number at least $R(s-1,t)$, or its blue neighbors number at least $R(s,t-1)$. Apply the appropriate smaller Ramsey number inside that neighborhood: either the opposite-color clique already exists, or a same-color clique extends by the chosen vertex. Thus $R(s,t)\le R(s-1,t)+R(s,t-1)$, proving finiteness by induction, in particular for $R(s)=R(s,s)$.

In a graph of maximum degree $d\ge 2$, a ball of radius $k-1$ about a vertex has at most ${\sum }_{j=0}^{k-1}{d}^j=(d^k-1)/(d-1)<d^k$ vertices. Hence a connected graph of order $d^k$ has a vertex outside this ball, at distance at least $k$. The argument also applies whenever the graph has at least $d^k$ vertices.

Now take a connected graph of order $R(s{)}^s$. If some vertex has at least $R(s)$ neighbors, apply the two-color Ramsey theorem to their pairs, coloring an edge red and a nonedge blue. A red $K_s$ is an induced complete graph, while a blue $K_s$ is an independent set of $s$ neighbors, which with the centre induces $K_{1,s}$. Otherwise the maximum degree satisfies $d<R(s)$. For $s\ge 2$, connectedness and the vertex count rule out $d\le 1$. The ball bound then provides vertices at distance at least $s$. A shortest path between them has no chord, since a chord would shorten it; its first $s$ edges induce $P_s$. The case $s=1$ is immediate. Therefore

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.

For example, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. ^[ref] present the neighbor argument and the sharp Ramsey number for triangles.

Equivalently, every graph on at least $R(s,t)$ vertices has an $s$-clique or a $t$-element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.

Let $A=R(k-1,\ell )$ and $B=R(k,\ell -1)$. From one vertex of any red-blue colored $K_{A+B}$, either at least $A$ incident edges are red or at least $B$ are blue. In the first case, apply the definition of the Ramsey number to its red neighbors: a red $K_{k-1}$ extends with the chosen vertex, and a blue $K_{\ell }$ is already enough. The blue case is analogous. This proves the recursion, with boundary values $R(k,2)=k$ and $R(2,\ell )=\ell$.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

Every red-blue colouring of the positive integers contains a monochromatic triple $x,y,z$ with $x+y=z$; the summands need not be distinct. Colour each edge $ij$ of $K_6$ by the colour of $|i-j|$. Since the Ramsey number $R(3,3)$ is at most $6$, there is a monochromatic triangle $i<j<k$. Its positive edge differences $j-i$, $k-j$ and $k-i$ have one colour and satisfy the required sum equation.