Ramsey theory

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 finite colouring of the positive integers contains a pair with nonzero square difference. One proof takes limits of the colour autocorrelations and represents the resulting positive-definite sequence by a positive spectral measure. Its atom at zero has mass at least the sum of squared colour densities. Averaging along squares kills irrational frequencies; a common multiple makes finitely many rational atomic frequencies equal to one. The remaining rational atomic mass can be made arbitrarily small, leaving a positive average correlation.

Let $R_k(3)$ be the least order of a complete graph whose every $k$-edge-colouring has a monochromatic triangle in a graph. At a vertex of a graph of order $k(R_{k-1}(3)-1)+2$, some colour joins at least $R_{k-1}(3)$ neighbours. An edge of that colour among these neighbours completes a triangle; otherwise the neighbours use at most $k-1$ colours and contain a triangle by induction. This proves the recurrence and the weaker explicit bound $R_k(3)\le 3k!$.

For a colouring $\chi :[S{]}^r\to \{0,\dots ,k-1\}$ of the $r$-element subsets of a set $S$, a subset $H\subseteq S$ is homogeneous if all its $r$-element subsets receive the same colour. The infinite Ramsey theorem for r-sets guarantees an infinite homogeneous subset when $S=\mathbb{N}$, $r$ is positive and the number of colours is finite. This does not guarantee a computable set when the colouring is computable.

A colouring is computable when an algorithm sorts the finite input subset, computes its colour and terminates. Its colour classes are uniformly computable sets. The distinction between existence of an infinite homogeneous set for a colouring and effective construction of one is a basic phenomenon in computability theory.

There is a two-colour computable colouring of pairs with no infinite computably enumerable set homogeneous for it. Enumerate these sets as $W_e$. In stages, give each eligible requirement two markers from its enumerated set, avoiding markers of higher priority, and cancel all lower-priority markers whenever a new assignment is made. Colour $(x,y)$ by the marker status of $x$ at stage $y$: first markers have colour zero, second markers colour one, and unmarked points colour zero. Each requirement is injured only finitely often by induction on its index. If $W_e$ is infinite it eventually has permanent distinct markers $a_e,b_e$; for every sufficiently large $y\in W_e$, the pairs $(a_e,y)$ and $(b_e,y)$ have different colours. Simulating finitely many stages computes each pair's colour, proving both effectiveness and the obstruction.

Let $K_s$ be an increasing uniformly computable finite approximation to the diagonal halting set. For $a<b<c$, colour the triple $0$ if $K_b\upharpoonright a=K_c\upharpoonright a$, and $1$ otherwise. No infinite homogeneous set for a colouring can have colour $1$, since the finitely many bits below its first element eventually stabilize. Every infinite homogeneous set $H$ of colour $0$ computes the diagonal halting set: choose $n<a<b$ in $H$ and read membership of $n$ in $K_b$. Homogeneity and unboundedness make this answer final. Thus the colouring has no infinite computable homogeneous set.

Colour $n>0$ by $(v_2(n)\mathrm{mod}2,\lfloor {\log }_{2}n\rfloor \mathrm{mod}2)$. No increasing infinite sequence can make all its sums $x_i+x_j$ and $x_i+2x_j$, $i<j$, one colour. If its 2-adic valuations are bounded, two terms of equal valuation and equal odd part modulo four give pair sums of different valuation parity. If they are unbounded, a later term divisible by a sufficiently large power of two prevents adding a fixed earlier term from crossing either dyadic boundary; the two resulting sums have adjacent logarithmic scale indices.

The space $[\mathbb{N}{]}^{\omega }$, also written ${\mathbb{N}}^{(\omega )}$, consists of all infinite subsets of the positive integers. An element is identified with its strictly increasing enumeration. If $s$ is finite, write $s⊏X$ when $s$ is the finite initial segment of this enumeration.

A finite stem is a finite initial segment $s$ of an infinite subset of $\mathbb{N}$. The associated neighbourhood in the ordinary topology on infinite subsets is $[s]=\{X:s\text{ is an initial segment of }X\}$. For an infinite tail $A$ above $\max s$, the neighbourhood $[s,A]=\{s\cup B:B\in [A{]}^{\omega }\}$ is basic in the Ellentuck topology. Finite stems allow a fusion argument to fix initial choices while successively thinning the remaining infinite tail.

A family $\mathcal{A}\subseteq [\mathbb{N}{]}^{\omega }$ is Ramsey in the homogeneous-cone sense if there is an infinite $M\subseteq \mathbb{N}$ such that either $[M{]}^{\omega }\subseteq \mathcal{A}$ or $[M{]}^{\omega }\cap \mathcal{A}=\varnothing$. This is the existence of one infinite homogeneous cone. Requiring such a refinement inside every infinite initial ground set gives the stronger definition used for a Ramsey set of infinite subsets; requiring a homogeneous refinement in every finite-stem neighbourhood gives a completely Ramsey set.

These quantifiers should be distinguished. For example, the existence of a homogeneous cone on the even numbers does not constrain a family's restriction to the odd numbers. If $\mathcal{E}$ is the finite-symmetric-difference parity colouring class on the odd numbers, the family consisting of $\mathcal{E}$ alone has a homogeneous cone disjoint from it on the even numbers, but no homogeneous cone on the odd numbers. Every open set in the ordinary topology on infinite subsets has homogeneous cones inside all infinite ground sets, as follows by deciding finite stems through fusion.

This topology has basic open sets $[A{]}^{\omega }$ for infinite ground sets $A$, without fixed finite stems. It is coarser than the Ellentuck topology and differs from the ordinary topology on infinite subsets, whose basic cylinders fix an initial segment. The symbol $\tau$ is sometimes used for either coarser convention, so it should be accompanied by a definition.

The whole space of infinite subsets of the natural numbers is a meagre set in the Ramsey cone topology. For $D_j=\{X:\min X=j\}$, the closure is $\{X:j\in X\}$, which has empty interior: every infinite ground set can be thinned to omit $j$. Thus all $D_j$ are nowhere dense, while their countable union is the whole space. In contrast, the whole space is not meagre in either the Ellentuck topology or the ordinary topology on infinite subsets.

A set $E\subseteq [\mathbb{N}{]}^{\omega }$ is Ramsey if every infinite $A$ has an infinite subset $B$ such that $[B{]}^{\omega }\subseteq E$ or $[B{]}^{\omega }\cap E=\varnothing$.

Every open set $O$ in the ordinary topology on infinite subsets is a Ramsey set of infinite subsets: some infinite $B$ has $[B{]}^{\omega }\subseteq O$ or $[B{]}^{\omega }\cap O=\varnothing$. Use acceptance and rejection of finite stems and fusion to decide every finite stem. If the empty stem is rejected, each rejected stem has only finitely many accepting one-point extensions. Successive avoidance of these finite obstructions gives an infinite set all of whose finite stems are rejected; openness then excludes every infinite subset from $O$. This concerns increasing enumerations of infinite subsets, rather than unrestricted sequences with repetitions.

Choose one representative $R$ for each equivalence class of infinite sets under finite symmetric difference. The colour $|A△R|\mathrm{mod}2$ changes on removing one point. Every cone $[M{]}^{\omega }$ therefore contains opposite-coloured sets $M$ and $M\setminus \{\min M\}$. Either colour family is a non-Ramsey set of infinite subsets. Choice of representatives is essential to this construction, which does not claim a definable regular family.

Using the axiom of choice, enumerate all infinite subsets $A_{\alpha }$ of the positive integers in order type $2^{{\aleph }_0}$. By transfinite recursion, choose two previously unused infinite subsets $X_{\alpha },Y_{\alpha }$ of each $A_{\alpha }$. This is possible because each $[A_{\alpha }{]}^{\omega }$ has cardinality $2^{{\aleph }_0}$ and fewer choices have been made at stage $\alpha$. The set $\{X_{\alpha }\}$ is not a Ramsey set of infinite subsets, since every $[A_{\alpha }{]}^{\omega }$ meets both it and its complement.

A set $E\subseteq [\mathbb{N}{]}^{\omega }$ is completely Ramsey if every basic Ellentuck topology neighborhood $[s,A]$ admits an infinite $B\subseteq A$ with $[s,B]\subseteq E$ or $[s,B]\cap E=\varnothing$. Keeping the finite stem $s$ makes this stronger than being a Ramsey set of infinite subsets.

Let E be the even positive integers, and take a finite-symmetric-difference parity colouring $\epsilon$ of $[E{]}^{\omega }$. The family $\{\{1\}\cup X:X\in [E{]}^{\omega },\epsilon (X)=0\}$ is Ramsey even under the every-ground-set convention, since every infinite ground set can be thinned to omit 1. It is not completely Ramsey: inside $[\{1\},E]$, every infinite tail has two subfamilies of opposite parity. Its supporting neighbourhood is closed and nowhere dense in the ordinary topology on infinite subsets, but open in the Ellentuck topology.

A set $N$ is completely Ramsey-null when every Ellentuck topology neighborhood $[s,A]$ has a refinement $[s,B]$ disjoint from $N$, with the same finite stem $s$. Assuming open Ellentuck sets are completely Ramsey, every star-nowhere dense set is completely Ramsey-null: apply the open-set property to the dense complement of its closure. The Ellentuck meagre-set fusion lemma shows that countable unions retain this avoidance property.

Countably many completely Ramsey-null sets can be avoided simultaneously in a stem-preserving Ellentuck topology refinement. Select an increasing sequence $b_j$ with nested infinite remaining tails. At stage $j$, thin the tail to avoid the $j$th set for every stem $s\cup t$, where $t$ ranges over all subsets of the first $j$ selected points. There are only finitely many such stems. Any infinite subset of the final selected sequence uses some such $t$ before stage $j$ and has all remaining points in the thinned tail. Thus it avoids every forbidden set. This explains why an argument checking only the full selected prefix is insufficient.

Every open set in the Ellentuck topology is a completely Ramsey set. Fix a finite stem $s$. An infinite tail accepts a finite extension $a$ if its entire basic neighborhood $[s\cup a,A]$ lies in the open set; it rejects $a$ if no infinite subtail accepts it. Decisions persist under thinning. A fusion chooses an infinite set deciding every finite extension. For any rejected extension, only finitely many possible next elements can yield accepted extensions, since infinitely many would themselves provide an accepting tail. A second thinning therefore makes all finite extensions rejected. Openness then rules out any point of the set in the resulting neighborhood.

Relative to a family $Y$, an infinite reservoir accepts a finite stem $s$ when its entire Ellentuck topology neighbourhood $[s,A]$ lies in $Y$. It rejects $s$ when no infinite refinement accepts it. Every reservoir has a refinement deciding a prescribed stem, and both outcomes are hereditary under further infinite thinning. These definitions turn open-set homogeneity into a fusion construction.

Suppose a reservoir rejects $s$ and decides every extension $s\cup \{a\}$. Only finitely many of those one-point extensions can have accepting tails. If infinitely many did, collect their new points into $C$; every infinite subset of $C$ begins with an accepting successor, so $[s,C]$ would lie in the family. That would make $C$ accept $s$, contradicting rejection. This finite-obstruction fact lets a second fusion preserve rejection of every finite stem.

Choose successive points and, after each choice, thin the unused reservoir to decide all subsets of the finite chosen prefix. There are only finitely many stems to handle at each stage. The final diagonal infinite set decides every one of its finite stems, because its relevant tail lies in the reservoir chosen when the stem's largest point was selected. The argument uses the hereditary decisions from acceptance and rejection of finite stems.

For a finite set $s$ and an infinite set $A$ lying above $\max s$, putThese sets form the basic neighborhoods of the Ellentuck topology, also called the star topology. It is finer than the ordinary topology on infinite subsets. Every basic neighborhood is a clopen set in the Ellentuck topology, and a closed set in the ordinary topology.

Every Borel set for the Ellentuck topology is completely Ramsey. First, an acceptance-and-rejection fusion makes every open set homogeneous after thinning the infinite reservoir while keeping its finite stem. Every nowhere-dense set is consequently completely Ramsey-null, and a fusion handling all subsets of each finite selected prefix shows that countable unions of such null sets remain null. Finally, sets differing from an open set by a meagre set form a sigma-algebra containing the open sets. Thus every Borel set has the required stem-preserving homogeneous refinement.

In the Ellentuck topology, suppose every open set is completely Ramsey and every meagre set is completely Ramsey-null. If $E△U$ is contained in a meagre set for some open $U$, first refine a basic neighbourhood without changing its stem to avoid that exceptional set, and then refine again to be homogeneous for $U$. The resulting neighbourhood is homogeneous for $E$. Sets with such an open representative form a sigma-algebra: countable unions collect the meagre errors, and complements replace $U^c$ by its interior, differing only on the nowhere-dense boundary of $U$. This proves that all star-Borel sets are completely Ramsey.

For an infinite coinfinite set $A\subseteq \mathbb{N}$, let $E_A=[A{]}^{\omega }$ in the space of infinite subsets of the natural numbers. This cone is a nonempty clopen set in the Ellentuck topology, because it is the basic neighbourhood $[\varnothing ,A]$, and any $X\notin E_A$ has a finite initial segment containing a point outside $A$ and hence a basic neighbourhood disjoint from $E_A$.

The cone is a closed set with empty interior in the ordinary topology on infinite subsets: membership of a point outside $A$ witnesses its complement as an open set, while every ordinary finite-stem neighbourhood can be extended by an arbitrarily large point outside $A$. Thus $E_A$ is an ordinary nowhere dense set, but it is neither ordinary open nor Ellentuck nowhere dense. It provides both distinctions between these two topologies.

The cone $[E{]}^{\omega }$ on the even integers is nonempty and Ellentuck topology open, while it is closed and nowhere dense in the ordinary topology on infinite subsets. Choose a finite-symmetric-difference parity colouring on that cone and take one colour class. The class is still ordinarily nowhere dense because its closure lies in the cone, but every stem-free refinement inside the cone meets both colours. Hence it is not completely Ramsey.

In the space of infinite subsets of the natural numbers, the families $C_n=\{X:n\notin X\}$ are clopen sets in the ordinary topology on infinite subsets and thus in the finer Ellentuck topology. Their union is $[\mathbb{N}{]}^{\omega }\setminus \{\mathbb{N}\}$. Every basic Ellentuck topology neighborhood of $\mathbb{N}$ contains $\mathbb{N}\setminus \{n\}$ for some sufficiently large $n$, so this union is not a closed set.

A subset of the space of infinite subsets of the natural numbers has this property when it differs from an Ellentuck topology open set by a meagre set in the same topology. By the complete-Ramsey characterization, these are precisely the completely Ramsey sets. Using meagreness from a different topology changes the definition.

The ordinary topology on $[\mathbb{N}{]}^{\omega }$ has basic sets $[s]=\{X:s⊏X\}$ for finite $s$. It is the product topology on increasing enumerations, and also the subspace topology on infinite-subset indicator functions in $\{0,1{\}}^{\mathbb{N}}$.

In the ordinary topology on infinite subsets, the family $D$ of cofinite sets is a countable set, a dense and a meagre set. Countability follows by indexing its members by their finite complements. Each singleton is closed with empty interior, while every basic cylinder with finite initial segment $s$ contains $s\cup \{n:n>\max s\}$. Consequently $D$ is not a nowhere dense set. This example uses the ordinary cylinder topology, rather than the Ramsey cone topology.

The family $D=\{\{a_1<a_2<\cdots \}:a_{n+1}>2a_n\text{ for all }n\}$ is ordinarily closed and nowhere dense. A failed gap is witnessed by a finite prefix, and any cylinder can be refined by adjoining consecutive large integers that fail the gap. Nevertheless $D$ intersects every infinite-subset cone in continuum many sets: a binary tree chooses two sufficiently large next points inside its reservoir at each step.

A closed nowhere dense family can meet every cone $[M{]}^{\omega }$ in continuum many sets, as the gap-doubling closed family of infinite subsets does. Well-order the cones and choose two fresh candidates in each, permanently reserving one of each colour. The red family meets every cone and its complement contains every reserved blue candidate, so it is not Ramsey. As a subset of the closed nowhere dense family, it is still nowhere dense and has the Baire property in the ordinary infinite-subset topology. This recursion requires no regularity assumption on the continuum cardinal.

A family $Y\subseteq [\mathbb{N}{]}^{\omega }$ is $\tau$-Baire when $Y△O$ is meagre for some ordinarily open family $O$. This is weaker than the corresponding regularity in the star topology. A meagre set meeting every Ramsey cone in both colours has the ordinary Baire property while failing to be a Ramsey set of infinite subsets.

For $r\ge s\ge 1$, the two-colour Ramsey number for disjoint edge matchings isThus every red-blue colouring of $K_{2r+s-1}$ contains either a red matching of size $r$ or a blue matching of size $s$, and the order is sharp.

For $t\ge 2$, the two-colour Ramsey number for $t$ vertex-disjoint triangles isEvery red-blue colouring of $K_{5t}$ therefore contains $t$ vertex-disjoint triangles of one colour, while a colouring of $K_{5t-1}$ can avoid such a packing in both colours.

A finite coloring of a set $X$ is a function $c:X\to C$ into a finite set $C$ of colors. A subset is monochromatic when the restriction of $c$ to it is constant.

The colour profile of a length-$N$ block $b_1,\dots ,b_N$ under a finite colouring $c$ is the ordered tuple $(c(b_1),\dots ,c(b_N))$. There are at most $r^N$ profiles when $c$ uses at most $r$ colours. Equally profiled blocks reproduce every colour configuration at the same relative positions; this converts a colouring of points into a finite colouring of blocks in the colour-focusing proof of Van der Waerden theorem.

A colour class of a finite colouring $c:X\to \{1,\dots ,r\}$ is a fibre $c^{-1}(i)$. Each colour class is a monochromatic set, and these fibres give a finite set partition of $X$ after empty fibres are omitted.

For $b>1$ and an integer $q\ge 2$, assign $x\ge 1$ the color $\lfloor {\log }_{b}x\rfloor \mathrm{mod}q$. The floor function partitions the domain into half-open geometric bins. If $1<{\log }_b(y/x)<q-1$, their bin indices differ by an integer in $\{1,\dots ,q-1\}$, so their colors differ. For example, $b=3/2$ and $q=3$ separates every ratio in $[1.9,2]$. Composing this finite coloring with another logarithm can obstruct monochromatic multiplicative configurations whose logarithms have such ratios.

A refinement of a finite coloring assigns different new colors whenever the original colors differ. A set monochromatic for the refinement is therefore monochromatic for the original coloring. Given colorings $\chi ,\psi$, the product coloring $n\mapsto (\chi (n),\psi (n))$ refines both. This makes it possible to impose finitely many coloring obstructions simultaneously.

A subset $A\subseteq X$ is monochromatic for a finite coloring $c:X\to C$ if there is a color $i\in C$ such thatEquivalently, the restriction of a function $c\upharpoonright A$ is a constant function, or $A$ lies in one colour class $c^{-1}(i)$. The word describes agreement of colors; it does not require $A$ to equal an entire colour class.

For example, color the integers by integer parity, using red for even and blue for odd. The set $\{2,4,8\}$ is monochromatic, whereas $\{2,3\}$ is not. If the colored objects are edges, a monochromatic triangle in a graph means that its three edges form a monochromatic set. In a coloring of $r$-element subsets of a set $S$, a homogeneous set for a colouring $H\subseteq S$ means that the collection of all $r$-element subsets of $H$ is monochromatic. For pairs, this is a complete graph on $H$ whose edges all have one color, rather than a coloring of the vertices in $H$.

The infinite form of Ramsey's theorem says that if the $r$-element subsets of an infinite set are finitely colored, then some infinite subset has all its $r$-element subsets in one color.

Take increasing even $u_i$ for which every ordered four-index expression $u_i+u_j+2u_k+2u_l$ has one colour. The Ramsey theorem for r-sets supplies them. Set $x_i=u_{2i-1}+u_{2i}$ and $y_i=(u_1+u_2)/2+2u_{i+2}$. Then both $x_i+2x_j$ and $y_i+y_j$ use the same ordered coefficient pattern $(1,1,2,2)$, so their union is monochromatic. The shared half-prefix makes the unweighted pair family possible without asking the two families to use the same generating sequence.

For finitely coloured $(r+1)$-element subsets, choose successive least points and use the inductive $r$-set theorem to thin the remaining reservoir after each choice. Every tuple with that least point then has one assigned colour. The infinite pigeonhole principle retains infinitely many least points with the same assigned colour, giving an infinite homogeneous set. The $r=1$ base case is the same pigeonhole principle. This proves the Ramsey theorem for r-sets for all finite $r$.

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 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.

Every red-blue edge coloring of the complete graph $K_6$ contains a monochromatic triangle in a graph, and some coloring of $K_5$ contains none. Together the five-cycle Ramsey coloring and six-vertex monochromatic triangle argument giveThe threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.

A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.

The small size makes exhaustive verification practical. The complete graph $K_5$ has $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ edges, giving $2^{10}=1024$ red-blue colorings of labeled vertices; exactly 12 have no monochromatic triangle in a graph. They are the choices of a red cycle graph of length five, whose blue complement graph is another five-cycle. The complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ triples in every coloring finds none without a monochromatic triangle in a graph; in fact the minimum number is two. These counts can be reproduced by assigning one bit to each unordered pair and testing whether the three bits of each triple agree. The monochromatic-triangle counting formula gives a separate explanation of the stronger minimum-two conclusion.

Place five labeled vertices around a pentagon. In the complete graph $K_5$, color the five perimeter edges red and the five diagonals blue. Writing $ij$ for the unordered pair $\{i,j\}$, the red pairs are $12,23,34,45,15$, and the blue pairs are $13,14,24,25,35$. This assigns a color to every pair, including every diagonal.

The red subgraph is the cycle graph $1,2,3,4,5,1$; the blue subgraph is the cycle graph $1,3,5,2,4,1$. Neither contains a triangle in a graph. Consequently, none of the ten triples has all three edges red or all three blue, proving the lower bound for the Ramsey number for triangles. Crossings in the drawing are not additional vertices.

Choose any vertex $v$ of a red-blue colored complete graph $K_6$. Its five incident edges go to the other five vertices. By the pigeonhole principle, at least three have the same color. Call their other endpoints $a,b,c$ and, after swapping color names if needed, suppose $va,vb,vc$ are red.

If any of $ab,ac,bc$ is red, it completes a red triangle in a graph with $v$. If none is red, all three are blue, so $a,b,c$ themselves form a blue triangle in a graph. Both possibilities force a monochromatic triangle in a graph. This proves the upper bound for the Ramsey number for triangles using only five incident edges and the three pairs among the selected neighbors; the colors of the other edges cannot defeat the argument.

Both panels show all 15 edges of a complete graph on six vertices. Faint colored edges are example choices outside the decisive argument; bold edges exhibit the forced triangle in a graph. The selected neighbor color could instead be blue, giving the same argument with the color names exchanged.

Let $p$ be prime and join two $p^2$-subsets of a $p^3$-element set when their intersection size is divisible by $p$. The modular intersection bound for a set family bounds both its independence and clique numbers by a quantity strictly below $p^{3p}$. Since the graph has $\left(\genfrac{}{}{0ex}{}{p^3}{p^2}\right)\ge p^{p^2}$ vertices,a lower bound larger than every fixed power of $p^{3p}$ as $p\to \infty$.

Let $X$ be a finite alphabet. A combinatorial line in $X^n$ is obtained by fixing some coordinates and replacing every coordinate in one nonempty active set by the same variable letter. It therefore contains one word for each letter of $X$.

For any proposed positive active size $d$, the displayed two-colour finite colouring of binary words gives opposite colours to the two points of every combinatorial line with exactly $d$ active coordinates. Their counts of the letter $2$ differ by $d$. Thus no dimension can guarantee a monochromatic line of one universally prescribed active size, even though the Hales-Jewett theorem guarantees some active size. The colouring is allowed to depend on $d$ because $d$ is chosen before the colouring.

For any $N\ge 1$, color $w\in [3{]}^N$ by its first letter together with its number of runs of a word modulo $3$. This finite coloring uses at most nine colors and has no monochromatic combinatorial line whose active coordinates form an interval. An active interval starting at the first coordinate changes the first letter. Otherwise, its left boundary and optional right boundary contribute $0$ versus $1$, $0$ versus $2$, or $1$ versus $2$ to the run count as the active letter varies. These differences remain nonzero modulo $3$. The first-letter component is essential for intervals that occupy the entire word.

Repeat every coordinate of a word $q$ times. A combinatorial line maps to a combinatorial line whose active-set size is multiplied by $q$. Pulling back a finite coloring along this map and using the Hales-Jewett theorem forces monochromatic lines with active-set size divisible by any prescribed positive integer $q$.

For a fixed alphabet size $m>1$, a family $\mathcal{F}\subseteq \mathcal{P}([n])$ is adequate if every two-color finite coloring of $[m{]}^n$ has a monochromatic combinatorial line whose nonempty active coordinate set belongs to $\mathcal{F}$.

An intersecting family is never adequate. Color a word red when the coordinates carrying letter $1$ contain a member of $\mathcal{F}$, and blue otherwise. For a line with active set $A\in \mathcal{F}$, its letter-$1$ word is red and its letter-$2$ word is blue, because no member of an intersecting family can lie wholly outside $A$.

For every finite alphabet $X$ and every positive integer $k$, there is $n$ such that every $k$-coloring of $X^n$ contains a monochromatic combinatorial line.

Induct on the alphabet size $k$. For an $r$-colouring, choose an $(k-1,k)$-insensitive combinatorial subspace whose dimension forces a monochromatic combinatorial line over the first $k-1$ letters. The inductive Hales-Jewett theorem supplies that line. Changing all of its active parameters from $k-1$ to $k$, one at a time, preserves the colour by the alphabet insensitivity lemma. Thus the line extends to all $k$ letters. The one-letter alphabet is the base case.

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

For r colours, k letters and d variable blocks, set $P_i={\sum }_{j<i}{L}_j$ and $L_i=r^{k^{P_i+d-i}}$. Process blocks from right to left. In block i, the $L_i+1$ words $a^t{b}^{L_i-t}$ have colour profiles indexed by all $k^{P_i}$ earlier words and $k^{d-i}$ later variable assignments. Two profiles agree, giving a nonempty variable interval insensitive to exchanging a and b. Previously obtained insensitivity holds for all earlier words and survives their restriction. This constructs the combinatorial subspace required by the alphabet insensitivity lemma.

A $d$-dimensional combinatorial subspace, also called a $d$-parameter set, has $d$ pairwise disjoint nonempty active coordinate sets. Coordinates in the $j$th active set all receive one freely chosen alphabet letter, independently for each $j$, while the remaining coordinates stay fixed.

For every alphabet size $m$, number of colors $k$, and dimension $d$, some $n$ has the property that every $k$-coloring of $[m{]}^n$ contains a monochromatic $d$-dimensional combinatorial subspace. It follows from the Hales-Jewett theorem by identifying $[m{]}^{dN}$ with the word space over the alphabet $[m{]}^d$.

A Hilbert $n$-cube in the positive integers is a setwhere $a,x_1,\dots ,x_n$ are positive integers.

Every finite coloring of the positive integers contains a monochromatic Hilbert cube of every prescribed finite dimension.

Every finite coloring of the positive integers contains monochromatic arithmetic progressions of every prescribed finite length.

For positive $r,k$, let $W(r,k)$ bound the interval needed to force a monochromatic length-$k$ arithmetic progression in every finite colouring using at most $r$ colours. The colour-focusing proof of Van der Waerden theorem inducts on $k$, simultaneously for every number of colours, and then creates progressions of distinct colours with a common next point.

Assume $W(r,k)$ exists for every $r$. For fixed $r$, construct $F_t$ such that a finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours of the form $f-h{d}_i$, $1\le h\le k$, with a common focus $f\in [F_t]$. Take $F_1=2W(r,k)$: a length-$k$ arithmetic progression in its first half has its next point inside the whole interval. For $k=1$, give a singleton step $1$.

Given $N=F_t$, put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Regard the first $M$ length-$N$ blocks as coloured by their full colour profiles. Some block indices $j_0,j_0+D,\dots ,j_0+(k-1)D$ share a profile. If there is no monochromatic length-$(k+1)$ arithmetic progression, this profile supplies $t$ focused progressions with focus position $f$, steps $d_i$, and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$. In the later block $j_{\ast }=j_0+kD\le 2M$, put $F=N(j_{\ast }-1)+f$. For each $i$, the points $F-h(ND+d_i)$ have colour $q_i$: they lie in the selected block $j_{\ast }-hD$ at position $f-h{d}_i$. The points $F-hND$ have colour $q$. Thus $t+1$ distinct colours focus at $F$. For $t=r$, its own colour completes one of the $r$ focused progressions. The base case $W(r,1)=1$ completes the mathematical induction.

For positive integers $k,s,\ell$, some $N$ ensures that every $k$-color finite coloring of $[N]$ contains a monochromatic setIt follows from the Van der Waerden theorem by mathematical induction on the number of colors. If $M$ is a bound for $k-1$ colors, take a long one-color arithmetic progression of length $(\ell -1)M+1$ and step $d$. Either one of $sd,2sd,\dots ,Msd$ has its color, giving the result immediately, or these multiples use only $k-1$ colors. Pull back their finite coloring to $[M]$ and use mathematical induction, then multiply the resulting configuration by $sd$. Enlarge the ambient finite integer interval to include all these multiples. The cases $k=1$ and $\ell =1$ are immediate. The parameter $s$ makes this useful for positive monochromatic solutions of a partition regular equation with arbitrary integer coefficients.

For all positive integers $k,m$, some $n$ has the following property: every $k$-coloring of $[n]$ contains $a,d>0$ for whichis monochromatic. Thus the common difference has the same color as the progression.

Several monochromatic arithmetic progressions are color-focused when they have different colors and extend by one further term to the same point. Such focused families give an elementary induction proof of the length-three case of the Van der Waerden theorem.

For every finite $S\subseteq {\mathbb{N}}^d$, every finite coloring of ${\mathbb{N}}^d$ contains a monochromatic homothetic copy $a+rS$. The theorem follows from the Hales-Jewett theorem by coloring a word according to the sum of the points indexed by its letters.

Every colouring of the positive integers, even with infinitely many colours, has an arithmetic progression of any prescribed finite length on which the colouring is constant or injective. Encode a progression by the equivalence relation of equality of its colours. This gives a finite colouring of its starting point and step. A Gallai theorem for an integer lattice copy of a suitable two-dimensional pattern makes either all indices inequivalent, or one equal-colour pair range independently over two whole progressions. In the second case, one of those progressions is monochromatic.

For a finite pattern $\{v_1,\dots ,v_k\}$ in a real vector space, pull a finite colouring back to words through the displayed sum map. A combinatorial line with active coordinates J maps to $a+|J|\{v_1,\dots ,v_k\}$. The Hales-Jewett theorem therefore forces a monochromatic homothetic copy. Integer patterns remain in the integer lattice; choosing b sufficiently large gives the positive-lattice version.

Every red-blue finite coloring of the pairs of positive integers has either a blue complete arithmetic progression of any prescribed finite length $m$, or two disjoint $m$-term arithmetic progressions with all cross-pairs red. To see the geometry, assign $(a,d)$ a chosen red pair of indices $(r,s)$ in its progression, assuming the first alternative fails. Apply the Gallai theorem for an integer lattice to the fixed finite patternIn a monochromatic copy $(a_0,d_0)+qF$ with common label $(r,s)$, the selected red pairs are preciselyThe copy lies in the positive quadrant, so $d_0>q(m-1)$. Consequently the two displayed arithmetic progressions are disjoint. Translating the finite pattern before applying the lattice theorem permits its initially negative coordinates.

A matrix $A$ over the rational numbers is partition regular when every finite coloring of the positive integers admits a monochromatic vector $x$ satisfying $Ax=0$, with every coordinate a positive integer. Repeated coordinates are permitted.

For any positive integer $c$, a homogeneous rational matrix is partition regular over $c\mathbb{N}$ if and only if it is partition regular over $\mathbb{N}$. Pull a colouring of $c\mathbb{N}$ back along $n\mapsto cn$ and scale the resulting solution. Conversely, restrict a colouring of all positive integers to $c\mathbb{N}$. The argument depends on homogeneity and does not automatically extend to inhomogeneous equations or prescribed distinctness conditions.

If a rational matrix $A$ is a partition regular matrix, every finite coloring of the positive integers admits monochromatic $y_1,\dots ,y_n$ such thatChoose a compactness bound for partition regularity $T$ for the number of colors, put $S=\mathrm{lcm}(1,\dots ,T)$, and pull back the coloring by $t\mapsto S/t$ on $[T]$. A monochromatic positive solution $x$ of $Ax=0$ gives $y_i=S/x_i$; then $(1/y_i)=x_i/S$. The least common multiple guarantees that every $y_i$ is a positive integer.

If a rational matrix is a partition regular matrix, then for each fixed number of colors $k$ some finite integer interval $[T]$ already forces a monochromatic positive solution. Otherwise the solution-free finite colorings of successive intervals form a finitely branching tree with every level nonempty. The König infinity lemma gives an infinite branch, contradicting partition regularity. More generally, this argument applies to any family of configurations each using finitely many positive integers.

For a partition regular matrix $A$ and any property $P$ of its positive solution vectors, either every finite coloring admits a monochromatic solution with $P$, or every finite coloring admits one without $P$. If the first alternative fails, take a witnessing coloring and pair it with any other coloring. Partition regularity of the product coloring forces a solution avoiding $P$ in the other coloring. The alternatives need not be exclusive.

If $c_1,\dots ,c_n$ are the columns of a matrix, the matrix has the columns property when $[n]$ has an ordered partition $B_1\bigsqcup \cdots \bigsqcup B_s$ such thatand, for $j>1$, ${\sum }_{i\in B_j}{c}_i$ belongs to the linear span of the columns indexed by $B_1\cup \cdots \cup B_{j-1}$.

Rado's theorem states that a rational matrix is partition regular if and only if it has the columns property.

The positive-variable system $3x+y=3z$, $x-2y=w$ is partition regular. Its columns for $x,z,w$ sum to zero, and the remaining $y$ column lies in their rational span, satisfying the columns condition. Thus every finite colouring has monochromatic positive $x,y,z,w$ with $2y<x$. A triangular m-p-c set gives the explicit solution $x=3u$, $y=3v$, $z=3u+v$, $w=3u-6v$, with positivity guaranteed by membership in that set.

For nonzero rational coefficients $a_1,\dots ,a_n$, the equationis partition regular exactly when some nonempty subset of the coefficients has sum zero. This is the one-row form of the columns property.

Suppose nonzero integer coefficients have a nonempty zero-sum subset $I$, and fix $i_0\in I$. Put $s=|a_{i_0}|$ and $C={\sum }_{j\notin I}{a}_j$. A Brauer progression theorem configuration containing a sufficiently long monochromatic progression of step $d$ and the point $sd$ gives a positive solution: take every outside variable equal to $sd$, and the inside variables from the progression with offsets ${\lambda }_i$, where ${\lambda }_{i_0}=-\mathrm{sgn}(a_{i_0})C$ and the other offsets are zero. Shifting all inside offsets by the same integer keeps their weighted sum unchanged, because ${\sum }_{i\in I}{a}_i=0$. This removes negative offsets while preserving the equation.

For nonzero integer coefficients $a_i$, choose a prime number $p>{\sum }_i|a_i|$ and colour each positive integer by its nonzero leading residue after removing its power of $p$. In a monochromatic zero-sum solution, divide by the least occurring power of $p$. Reduction modulo $p$ then makes the sum of the coefficients attached to the least-valuation variables vanish modulo $p$. Its absolute value is less than $p$, so that sum vanishes as an integer. This gives the necessity direction of the one-equation partition regularity criterion without using the general Rado theorem.

A rational homogeneous equation ${\sum }_i{a}_i{x}_i=0$ has a monochromatic positive odd solution in every finite colouring of the odd integers exactly when its full coefficient sum is zero. Sufficiency uses a constant odd vector. For necessity, clear denominators and, if the total $S$ is nonzero, colour by odd residue classes modulo $2^K>|S|$. A common odd residue is invertible, so a solution would require $2^K\mid S$, impossible. This is stronger than the zero-sum-subset criterion for unrestricted partition regularity.

The necessity direction in Rado's theorem colors an integer using initial data from a P-adic valuation. Applying partition regularity and grouping the coordinates of a monochromatic solution by valuation yields the blocks in the columns property; reduction modulo successively higher powers of $p$ supplies the required linear dependences.

After clearing denominators in a matrix, for every disjoint pair of index sets $I,B$ with $B$ nonempty and ${\sum }_{i\in B}{a}_i$ outside the linear span of the $I$-columns, choose an integer linear functional vanishing on those columns but not on the indicated sum. Choose a prime number dividing none of the finitely many nonzero evaluations. The last nonzero digit coloring for this prime, applied to a monochromatic positive solution, groups coordinates into blocks by P-adic valuation. Applying the appropriate functional and reducing modulo the prime shows that each block sum lies in the linear span of all earlier columns. This proves necessity in Rado's theorem without an asymptotic limiting argument.