Chapter 21: Ramsey Theory

Must every long colored sequence contain a monochromatic progression?

Color each position of a sequence red or blue. Can both colors keep avoiding three equally spaced positions forever? A long monochromatic run would certainly contain such a pattern, but a coloring can alternate, switch in blocks, or look irregular. The question is whether any strategy can avoid the pattern once the sequence is sufficiently long.

A $k$-term arithmetic progression is

$$ a,a+d,\ldots,a+(k-1)d,\qquad a\ge1,\quad d\ge1. $$

The positive difference makes its terms distinct. A progression is monochromatic when all its terms receive the same color. Ramsey theory studies patterns that every coloring must contain, and constructions that postpone them. Its objects can be positions, graph edges, hyperedges, or words; the object being colored must always be specified.

We will prove elementary graph and infinite Ramsey results, trace arithmetic examples, and then distinguish word, equation, and higher-uniformity extensions. An upper bound requires an argument covering every coloring; a lower bound requires one coloring that avoids the target. Keeping those two jobs separate is the central habit of this chapter.

21.1 Classical finite Ramsey theorem

Write $K_N$ for the complete graph on $N$ vertices. Define $R(s,t)$ as the least $N$ such that every red-blue coloring of its edges contains a red $K_s$ or a blue $K_t$. A clique is monochromatic when all its edges have one color; its vertices are not themselves colored. Assume $s,t\ge2$.

Finite Ramsey theorem, graph form. The number $R(s,t)$ exists for every such pair, and

$$ R(s,t)\le R(s-1,t)+R(s,t-1),\qquad s,t\ge3. $$

Proof mechanism: focus on one vertex. Put $a=R(s-1,t)$, $b=R(s,t-1)$, and consider a coloring on $a+b$ vertices. Fix $v$. Among its $a+b-1$ incident edges, either at least $a$ are red or at least $b$ are blue, since otherwise there would be at most $(a-1)+(b-1)$ neighbors.

In the red neighborhood, the definition of $a$ gives a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. In the blue neighborhood, the corresponding alternatives are a red $K_s$ or a blue $K_{t-1}$ extending with $v$. This proves the recursion. The bases $R(2,t)=t$ and $R(s,2)=s$ follow because avoiding the color of the two-vertex target forces every edge to have the other color. Induction on $s+t$ therefore proves finiteness.

Pascal's identity also gives the explicit classical bound

$$ R(s,t)\le\binom{s+t-2}{s-1}. $$

Its boundary values agree with the bases, and each interior binomial is the sum of its two predecessor binomials. A convenient diagonal consequence is $R(s,s)\le\binom{2s-2}{s-1}\le4^{s-1}$. These are elementary upper bounds, not exact formulas.

Solved example: $R(3,3)=6$. At a vertex of $K_6$, at least three of its five incident edges have the same color. Suppose they are red, leading to $a,b,c$. A red edge among these three creates a red triangle with the original vertex; if there is none, $abc$ is blue. Swapping color names handles the other case.

For the lower bound, color the five edges of a cycle on $[5]$ red and all remaining edges blue. The red graph is a 5-cycle and the blue graph is another 5-cycle, so neither has a triangle. This coloring shows $R(3,3)\gt5$, and the universal argument gives $R(3,3)\le6$.

Exercise. Use the recursion to bound $R(3,4)$. Hint: use $R(2,4)=4$ and $R(3,3)=6$. Solution: $R(3,4)\le10$. The calculation alone does not prove equality.

21.2 Multicolor Ramsey numbers

For $q$ named edge colors and targets $s_1,\ldots,s_q\ge2$, define $R(s_1,\ldots,s_q)$ as the least $N$ such that every coloring of $K_N$ contains a clique of size $s_i$ in color $i$ for some $i$. Write $R_q(s)$ when all targets equal $s$; thus $R_2(s)=R(s,s)$. A coloring may use fewer than its available $q$ colors.

If all $s_i\ge3$, the same neighborhood proof gives

$$ R(s_1,\ldots,s_q)\le \sum_{i=1}^q R(s_1,\ldots,s_i-1,\ldots,s_q)-q+2. $$

To check the extra constant, denote the $i$th summand by $a_i$. With $N=\sum_i a_i-q+2$, there are $\sum_i(a_i-1)+1$ neighbors of a vertex, forcing some color-$i$ neighborhood to have at least $a_i$ vertices. Its Ramsey alternative either already supplies another color's target or supplies color $i$'s smaller target to extend. If a target is 2, either an edge in that color finishes the problem or that color is absent, reducing to fewer colors. Induction proves multicolor finiteness.

Solved construction. On vertices $0,1,2,3$, color pairs 01,23 red, 02,13 blue, and 03,12 green. Each color class is a matching, so no triangle is monochromatic. Consequently $R_3(3)\gt4$. Inspecting this example does not give the exact threshold.

Exercise. Why is $R(2,3,3)=6$? Hint: distinguish whether a red edge exists. Solution: a red edge already supplies the first target; without red edges, this is the blue-green triangle problem on six vertices. The avoiding two-color 5-cycle construction shows the matching lower bound.

21.3 Infinite Ramsey theorem

Let $\mathbb N=\{1,2,\ldots\}$ and let $\binom Xr$ denote the $r$-element subsets of $X$. The infinite Ramsey theorem states: for every fixed positive integer $r$, every coloring $c:\binom{\mathbb N}r\to[q]$ with finitely many colors has an infinite set $Y$ on which all $r$-subsets have one color. Such a set is homogeneous. It need not be an interval or an arithmetic progression.

Complete proof for pairs. Start with an infinite reservoir $X_0$. Choose its least element $v_1$. Partition the remaining elements by the color of $v_1x$; the infinite pigeonhole principle gives an infinite color class $X_1$ and its color $\gamma_1$. Choose the least $v_2\in X_1$ and repeat, retaining an infinite $X_2\subseteq X_1\setminus\{v_2\}$ on which $v_2x$ has one color $\gamma_2$. Continue.

For every $i\lt j$, the later vertex $v_j$ belongs to $X_i$, so

$$ c(\{v_i,v_j\})=\gamma_i. $$

One of the finitely many values of $\gamma_i$ occurs for infinitely many indices $I$. Then $Y=\{v_i:i\in I\}$ is infinite and homogeneous: the color of each pair is the common value at its earlier index. We never require the intersection of all reservoirs to be infinite or nonempty; the selected vertices give the desired set.

Extension to fixed $r$. For $r=1$, this is infinite pigeonhole. Assuming the theorem for $r-1$, choose a pivot $v_i$ from an infinite reservoir and color its $(r-1)$-subsets $S$ by $c(S\cup\{v_i\})$. The induction hypothesis gives an infinite homogeneous subreservoir with extension color $\gamma_i$. Continue with nested reservoirs, then retain infinitely many pivots having one extension color. In any $r$-set of retained pivots, all the other vertices lie in the subreservoir of the first pivot. Its color is therefore that pivot's common extension color. This proves the theorem by induction on uniformity.

Solved example. Color a pair $\{i,j\}$, with $i\lt j$, red if $i$ is even and blue if $i$ is odd. All even positive integers form an infinite red homogeneous set; all odd positive integers form an infinite blue one. Starting at 2, the reservoir construction below selects $2,3,4,5,6,\ldots$, with extension colors alternating red and blue. Retaining the even pivots works.

The SVG shows a finite prefix of this exact coloring and the first three vertices of the resulting red set. Its left table records the extension-color invariant; the right triangle displays all three pair incidences. The infinite proof justifies continuing the pattern, whereas a finite diagram alone cannot prove an infinite assertion.

Exercise. Why must the number of colors be finite? Hint: try coloring a pair by its smaller element. Solution: the coloring $c(\{i,j\})=\min(i,j)$ uses infinitely many colors. In any three vertices $a\lt b\lt c$, the pairs $ab$ and $bc$ have different colors, so there is no infinite homogeneous set.

21.4 Van der Waerden's theorem

For positive integers $q,k$, van der Waerden's theorem states that some $N$ forces a monochromatic $k$-term arithmetic progression in every coloring $c:[N]\to[q]$. Define $W(q,k)$ as the least such $N$. Equivalently, every finite coloring of $\mathbb N$ contains arbitrarily long monochromatic arithmetic progressions; the progression's color may depend on its length.

The order of quantifiers is

$$ \forall q,k\quad\exists N\quad\forall c:[N]\to[q]\quad \exists a,d\ge1:\ a+(k-1)d\le N\text{ and }c(a)=\cdots=c(a+(k-1)d). $$

It does not assert an infinite monochromatic arithmetic progression with one fixed starting point and difference. Nor does infinite Ramsey on arbitrary subsets directly impose equal spacing. Arithmetic structure is an additional requirement.

Proof mechanism. Classical proofs use color focusing: arrange translated and dilated configurations so that failure to produce the target forces several controlled color patterns around a common configuration. Repeating the process eventually exceeds the finite supply of colors. The bookkeeping proving that all required configurations fit into a finite interval is substantial. A different exact route is the word-to-progression reduction in Section 21.6: Hales–Jewett forces a variable-word line, and summing its coordinates produces an arithmetic progression. That reduction is fully proved there; the general word theorem is explicitly treated as an advanced theorem. For a primary proof that also develops a stronger density result, see D. H. J. Polymath, A new proof of the density Hales–Jewett theorem.

Solved finite case: $W(2,3)=9$. The opening coloring proves $W(2,3)\ge9$. To certify the upper bound, let $\mathcal A_n$ be all red-blue strings of length $n$ with no monochromatic three-term progression. Start with the empty string. To form $\mathcal A_{n+1}$, append each of the two colors to each string in $\mathcal A_n$, rejecting an extension exactly when

$$ c(n+1-2d)=c(n+1-d)=c(n+1) $$

for some positive $d$ with $n+1-2d\ge1$. This is a complete recurrence: any newly created progression must end at the new position. The counts for lengths 0 through 9 are

$$ 1,2,4,6,10,14,20,16,6,0. $$

The six surviving length-eight strings, paired by swapping colors, are displayed below. Every extension fails with the indicated witness, completing a reproducible finite certificate.

This recurrence and its exhaustive evaluation establish a small exact value. They do not replace the theorem's general existence proof for arbitrary $q,k$.

Exercise. In a coloring of $[6]$ by parity, find a monochromatic three-term progression and identify its difference. Hint: progressions need not be consecutive. Solution: 1,3,5 and 2,4,6 work, both with difference 2.

21.5 Schur's theorem and arithmetic Ramsey theory

Schur's theorem states that every finite coloring of the positive integers has positive integers $x,y,z$ of one color satisfying $x+y=z$. Repeated variables are allowed: $x=y$ is a legitimate solution. For fixed $q$, there is a finite threshold $N$ forcing a solution in $[N]$.

Complete proof from graph Ramsey. Let $M=R_q(3)$, and color the positive integers up to $M-1$ with $q$ colors. On graph vertices $0,1,\ldots,M-1$, color the edge $ij$ by the color of the positive difference $|i-j|$. Graph Ramsey gives a monochromatic triangle on $a\lt b\lt c$. Set

$$ x=b-a,\qquad y=c-b,\qquad z=c-a. $$

All three are positive, all are at most $M-1$, their colors are the triangle's edge colors, and $x+y=z$. This proof converts a homogeneous graph configuration into an arithmetic equation through differences. It yields the threshold $R_q(3)-1$, without asserting that this bound is sharp.

Solved two-color threshold. On $[4]$, color 1 and 4 red, 2 and 3 blue. There is no monochromatic solution: the only sums within $[4]$ are $1+1=2$, $1+2=3$, $1+3=4$, and $2+2=4$, and none has all terms one color.

Conversely, suppose $[5]$ has no solution and rename the color of 1 red. Then 2 must be blue because $1+1=2$, and 4 must be red because $2+2=4$. The equation $1+4=5$ forces 5 blue. If 3 is red, $1+3=4$ is a red solution; if 3 is blue, $2+3=5$ is a blue solution. Both possibilities contradict avoidance. Thus five is the least forcing interval length under this convention.

Some references define the two-color Schur number as the greatest avoiding interval length, which is 4. State the convention before quoting a number.

Arithmetic progressions and Schur triples encode different equations: $a+c=2b$ imposes equal spacing, while $x+y=z$ expresses addition. An arbitrary homogeneous set from infinite Ramsey need not solve either equation. The difference encoding above is the bridge supplying the required arithmetic structure.

Exercise. Why is coloring odd integers red and even integers blue not a Schur-avoiding coloring? Hint: repeated summands are permitted. Solution: $2+2=4$ is entirely blue.

21.6 Hales–Jewett theorem

Optional advanced elective. This section is not required for the chapter foundation. Its finite words provide a common language for several arithmetic Ramsey patterns. Let $[k]^n$ be the words of length $n$ over the alphabet $\{1,\ldots,k\}$. A combinatorial line is specified by a nonempty set $J\subseteq[n]$ of variable positions and fixed letters outside $J$. Its $k$ words are obtained by filling every position in $J$ with the same letter $x$, once for each $x\in[k]$.

The variable positions change together, not independently. For example, the template *2*1 over $[3]$ gives exactly

$$ 1211,\qquad2221,\qquad3231. $$

It does not give all nine ways to choose the first and third letters independently. A line's variable set must be nonempty, or it would consist of a single repeated word.

Hales–Jewett theorem. For every alphabet size $k$ and finite color count $q$, there exists $n$ such that every coloring of $[k]^n$ with $q$ colors contains a monochromatic combinatorial line. Denote the least such dimension by $\operatorname{HJ}(k,q)$. These are word colorings, not edge colorings of a graph. The ordinary theorem and a stronger density theorem are treated in D. H. J. Polymath's primary paper.

Complete binary case. For $k=2$, take $n=q$ and consider the $q+1$ words $w_j$ whose first $j$ letters are 2 and remaining letters are 1, for $0\le j\le q$. Two words $w_i,w_j$, with $i\lt j$, have the same color. They form a combinatorial line with variable block $\{i+1,\ldots,j\}$, fixed prefix of 2s, and fixed suffix of 1s. Thus $\operatorname{HJ}(2,q)\le q$.

For the matching lower bound, when $n=q-1$ color a word by its number of 2s modulo $q$. The two words of any line differ in that number by $|J|$, between 1 and $q-1$, so their colors differ. Hence $\operatorname{HJ}(2,q)=q$, including the trivial one-color case.

General proof mechanism, with an omitted lemma. A combinatorial subspace uses several disjoint nonempty variable blocks whose letters vary independently. An insensitivity lemma produces a high-dimensional subspace where swapping letters $k-1$ and $k$ in its variable coordinates does not change the color. Restrict to alphabet $[k-1]$, apply induction on alphabet size to obtain a line, and use insensitivity to add its $k$th word with the same color. The nontrivial omitted ingredient is the insensitivity lemma, including its dimension estimates; this paragraph is a proof sketch, not a derivation of the full theorem from pigeonhole alone.

Exact bridge to van der Waerden. Let $n=\operatorname{HJ}(k,q)$ and color $[kn]$ with $q$ colors. Give a word $w$ the color of its coordinate sum $\sum_i w_i$. A monochromatic line with variable set $J$ has sums

$$ A+|J|,\ A+2|J|,\ldots,A+k|J|, $$

where $A$ is the sum of its fixed coordinates. These are a monochromatic $k$-term progression with positive difference $|J|$, all in $[kn]$. Thus $W(q,k)\le k\operatorname{HJ}(k,q)$. The sum map need not be injective on all words; it is injective along this line because its sums increase strictly.

For *2*1, the sums are $5,7,9$. If its three words are monochromatic under the sum coloring, that progression is monochromatic in the original interval. A line in an unrelated word coloring would not automatically imply colors for integers; the induced coloring is part of the argument.

Exercise. List the line 1** over $[3]$ and its sums. Hint: use one common letter in both stars. Solution: the words are 111, 122, 133, with sums $3,5,7$ and difference 2.

21.7 Rado's theorem on partition-regular equations

Optional advanced elective. Let $A$ be an integer matrix with $m$ rows and $\ell$ columns. The homogeneous system $A\mathbf x=\mathbf0$ is partition regular over the positive integers if, for every finite coloring of $\mathbb N$, it has a solution $\mathbf x\in\mathbb N^\ell$ whose entries all have the same color. Positivity excludes the automatic zero solution. Equal entries are allowed unless distinctness is separately imposed.

Write the columns as $\mathbf a_1,\ldots,\mathbf a_\ell$. The columns condition requires an ordered partition of their indices into nonempty blocks $I_1,\ldots,I_t$ such that

$$ \sum_{i\in I_1}\mathbf a_i=\mathbf0, $$

and, for each $j\ge2$,

$$ \sum_{i\in I_j}\mathbf a_i\in \operatorname{span}_{\mathbb Q}\{\mathbf a_i:i\in I_1\cup\cdots\cup I_{j-1}\}. $$

The span uses the individual earlier columns, not merely the earlier block sums. The block order is part of the witness.

Rado's theorem. Such a finite homogeneous integer system is partition regular over $\mathbb N$ if and only if its matrix satisfies the columns condition. This equivalence quantifies over all finite color counts; failure of the condition does not mean every particular coloring avoids solutions. A primary modern extension that states the classical condition explicitly is Robertson, A Multidimensional Rado Theorem.

Solved example: Schur's equation. For $x+y-z=0$, the columns are the scalars $1,1,-1$. Choose $I_1=\{1,3\}$ and $I_2=\{2\}$. The first sum is zero, and the second is 1, which lies in the rational span of the earlier columns $1,-1$. Rado therefore recovers Schur partition regularity. The full proof for this particular equation was already supplied by the difference-colored triangle.

A failure with an explicit avoiding coloring. For $x-2y=0$, no nonempty subset of the two columns $1,-2$ sums to zero, so the columns condition fails. Write each positive integer uniquely as $2^a u$ with $u$ odd, and color it by the parity of $a$. Doubling changes the color. Therefore $x=2y$ never has same-colored entries in this two-coloring, directly verifying nonregularity.

Proof mechanism, with prerequisites omitted. Sufficiency constructs structured monochromatic sets whose levels let the first block cancel and later blocks be corrected using earlier columns. A standard route uses Deuber's theorem on special finite sets. Necessity uses finite colorings encoding leading digit and scale information to force a columns-condition witness from any monochromatic solution. The multiscale construction and its parameter choices are omitted here; the cited paper explains the connection with Deuber's theorem. Neither direction follows just by finding one numerical solution.

The progression equation $x-2y+z=0$ has column sum zero, so it satisfies the condition. However, $x=y=z$ is already a solution. Rado's stated theorem does not itself guarantee a nonconstant three-term progression. Van der Waerden supplies that stronger conclusion, including a positive difference. This illustrates why a distinctness requirement materially changes a statement.

Exercise. Check the columns condition for $x+y=2z$. Does the condition alone justify claiming $x\ne y$? Hint: add the three columns. Solution: $1+1-2=0$, so one block containing all indices works. The theorem as stated allows $x=y=z$ and makes no distinctness claim.

21.8 Canonical and structural Ramsey theory

Optional research extension. Ordinary Ramsey theory assumes finitely many colors and seeks one color. Canonical Ramsey theory permits arbitrarily many color names and seeks a controlled equality pattern among colors instead. Structural Ramsey theory colors copies of one finite structure inside a larger structure and seeks a copy of another structure on which those smaller copies are monochromatic.

For pairs of an ordered set, the canonical Ramsey theorem says that for every target size $s$ there is a finite $N$ such that every coloring of $\binom{[N]}2$, without a bound on its color count, has an $s$-vertex subset with one of four canonical patterns:

In the endpoint patterns, different relevant endpoints must give different colors. Saying that the color depends on an endpoint without this distinction would allow further accidental equalities and would not specify the canonical form.

Solved finite patterns. On ordered vertices $1,2,3,4$, color every pair red for the constant form; color $ij$ by $i$ for the smaller-endpoint form; color it by $j$ for the larger-endpoint form; or give the six pairs six distinct labels for the rainbow form. The smaller-endpoint pattern uses colors 1, 2, and 3 with multiplicities 3, 2, and 1. It need not contain a monochromatic triangle: the three edges on $a\lt b\lt c$ have colors $a,a,b$. That is why canonical patterns broaden the conclusion when color names are unrestricted.

For structural language, write $C\to(B)^A_q$ when every $q$-coloring of copies of $A$ in $C$ leaves a copy of $B$ whose internal copies of $A$ all have one color. A class has the Ramsey property if it supplies such a $C$ for every $A,B$ in the class and every finite $q$.

Established structural theorem. The class of finite linearly ordered graphs has this property, with copies taken through order-preserving induced embeddings. The ambient graph $C$ is not required to be complete; preserving nonedges matters. A full primary treatment and further classes appear in Mašulović, Canonizing structural Ramsey theorems and Hubička and Nešetřil, All those Ramsey classes.

Concrete instance. Take $A$ to be an ordered edge, $B$ an ordered triangle, and $q=2$. Choosing $C$ as $K_6$ with any vertex order works by $R(3,3)=6$. All three pairs in a selected triangle are copies of $A$. This checks one structural instance, not the theorem for all ordered graphs; for example, a noncomplete $B$ cannot appear as an induced subgraph of a complete $C$.

Proof sketch, with prerequisites omitted. Canonical proofs first stabilize finite equality patterns of edge colors, then classify which stabilized patterns are consistent. Structural proofs use partite constructions and amalgamation to assemble copies while preserving the required relations and nonrelations. The classification, partite lemma, and amalgamation machinery are omitted. The ordinary clique recursion does not alone prove these extensions.

Research snapshot, checked 11 October 2026. The June 2026 preprint Azócar Carvajal, Basu, Reiher, Rödl, Santos, and Schacht, Canonical Ramsey theorem for graphs with clean intersections proves a construction in which an arbitrary edge coloring yields a canonical induced copy of a prescribed ordered graph, while designated copies meet only in a vertex, an edge, or not at all. This is a theorem reported in the preprint, with stronger control of the ambient construction, rather than a conjecture. It also illustrates a research direction beyond merely reducing an ordinary Ramsey number.

Exercise. In the smaller-endpoint coloring on $[4]$, list the colors of 12, 14, and 24. Hint: use the first endpoint. Solution: they are 1, 1, and 2. The first two edges agree in color because their smaller endpoint is the same; 24 does not.

21.9 Probabilistic lower bounds for Ramsey numbers

A construction need not be specified edge by edge to prove that it exists. The first-moment method shows that an undesirable configuration count is zero for at least one outcome when its expectation is less than 1. Section 22.3 is recommended later background; only elementary independence and linearity of expectation are needed here. The argument below is complete. For developments beyond this classical estimate, see Campos, Griffiths, Morris, and Sahasrabudhe, An exponential improvement for diagonal Ramsey.

Color each edge of $K_N$ independently red or blue with equal probability. For a fixed $s$-vertex set, its $\binom s2$ edges are all red with probability $2^{-\binom s2}$ and all blue with the same probability. For $s\ge2$, those events are disjoint. If $X$ counts monochromatic $K_s$ vertex sets, then

$$ \mathbb E X=\binom Ns2^{1-\binom s2}. $$

The indicators for overlapping cliques need not be independent; linearity of expectation does not require that. If the displayed quantity is less than 1, some coloring has $X=0$: otherwise the nonnegative integer $X$ would always be at least 1 and so would its expectation. Therefore

$$ \binom Ns2^{1-\binom s2}\lt1\quad\Longrightarrow\quad R(s,s)\gt N. $$

Solved numerical bound. With $s=5$ and $N=11$,

$$ \mathbb E X=\frac{\binom{11}{5}}{2^9}=\frac{462}{512}=\frac{231}{256}\lt1. $$

Hence $R(5,5)\ge12$. This estimate is intentionally elementary and does not assert the exact value. Markov's inequality also gives $\Pr(X=0)\ge1-231/256=25/256$, so a uniformly random attempt has a positive, explicitly bounded success probability. Checking each sampled coloring is still necessary if an actual witness is requested.

For a simple asymptotic consequence, choose $N=\lfloor2^{s/2}\rfloor$ and use $\binom Ns\le N^s/s!$. Then

$$ \mathbb E X\le\frac{2^{1+s/2}}{s!}\lt1\qquad(s\ge3). $$

At $s=3$ the last inequality holds, and each next ratio is multiplied by $\sqrt2/(s+1)\lt1$. Thus $R(s,s)\gt\lfloor2^{s/2}\rfloor$ for every $s\ge3$. Combining this with the elementary upper bound gives exponential lower and upper benchmarks with different bases. Stronger estimates require stronger arguments.

Verified improvement, not an optimality claim. The cited Campos–Griffiths–Morris–Sahasrabudhe paper proves $R(s,s)\le(4-\varepsilon)^s$ for a fixed positive $\varepsilon$. Thus the classical base-4 bound taught above should not be labeled the best known upper bound. This chapter does not need a current sharp numerical base to explain the first-moment proof.

Exercise. For $s=4$, find the largest $N$ certified by the exact first-moment inequality. Hint: compare $\binom N4$ with $2^5=32$. Solution: $N=6$ works since $15/32\lt1$; $N=7$ fails since $35/32\gt1$. Failure of the inequality is failure of this sufficient test, not proof that no avoiding coloring exists.

21.10 Hypergraph Ramsey problems and asymptotic bounds

Optional research extension. Chapter 20 introduced $r$-uniform Ramsey numbers. Write $R_r(s,t)$ for the least $N$ forcing a red $K_s^{(r)}$ or a blue $K_t^{(r)}$ in every coloring of $\binom{[N]}r$, and $R_r(s)=R_r(s,s)$. Here the subscript is uniformity, unlike $R_q(s)$ in Section 21.2, where it counts graph edge colors. Keep the convention visible when comparing statements. Assume $s,t\ge r$.

Solved five-vertex construction. Color pairs of $[5]$ red on the cycle 12,23,34,45,15 and blue otherwise. Color a triple by the color of its complementary pair in $[5]$. Each four-set omits one vertex $v$; its four triples correspond exactly to the four pairs incident to $v$. The cycle gives $v$ two red and two blue incident pairs. Thus every four-set has two triples of each color and no monochromatic tetrahedron occurs. Consequently $R_3(4)\gt5$.

For instance, on $\{1,2,3,4\}$ the red triples are 123 and 234, whose complementary pairs are 45 and 15; the blue triples are 124 and 134. This is a hyperedge coloring, not a weak vertex coloring of a 3-graph.

Random lower bound. Independently color every $r$-subset red or blue. Counting monochromatic $s$-vertex complete $r$-graphs gives

$$ \mathbb E X=\binom Ns2^{1-\binom sr}. $$

Whenever this is less than 1, $R_r(s)\gt N$. For triples, set $N=\lfloor2^{(s-1)(s-2)/12}\rfloor$. The estimate $\binom Ns\le N^s/s!$ gives

$$ \mathbb E X\le\frac{2^{1-\binom s3/2}}{s!}\lt1\qquad(s\ge3). $$

Thus the elementary argument already yields $R_3(s)\ge2^{c s^2}$ for some positive constant $c$ and sufficiently large $s$. This scale differs from the graph first-moment scale because a fixed $s$-set now contains $\binom s3$ independently colored objects.

Upper bound by extension stabilization. The reservoir proof in Section 20.6 gives, for $r\ge2$ and $s\gt r$,

$$ R_r(s)\le(M+1)2^{\binom M{r-1}},\qquad M=R_{r-1}(s-1). $$

Each selected $(r-1)$-set fixes the color of all its future extensions by retaining a largest color class; a homogeneous set in the derived lower-uniformity coloring extends by a final reservoir vertex. There are $\binom M{r-1}$ possible restrictions, accounting for the exponential cost. For $r=3$, the graph estimate $M\le4^{s-2}$ makes this at most double exponential in $s$. For $s=4$, substituting $M=6$ gives the concrete, deliberately loose bound $R_3(4)\le7\cdot2^{15}=229376$.

Define the tower functions by $T_1(x)=x$ and $T_{j+1}(x)=2^{T_j(x)}$. Classical bounds for fixed $r\ge4$ have the form

$$ T_{r-1}(c_r s^2)\le R_r(s)\le T_r(C_r s) $$

for positive constants and sufficiently large $s$. These are valid classical benchmarks, not a claim about current sharpest constants. Conlon, Fox, and Sudakov, Hypergraph Ramsey numbers records these bounds and the stepping-up framework. Their different tower heights describe a limitation of these bounds; they do not establish an exact growth rate.

Stepping-up mechanism, proof sketch. The construction replaces a ground set of $m$ positions with $2^m$ binary words. For ordered words $u\lt v$, let $\delta(u,v)$ be the highest bit position where they differ. Consecutive differences and their local extrema control the color of higher-uniformity subsets, transferring an avoiding coloring from the positions. For example, the ordered binary integers $0,3,4,7$ have consecutive differences $1,2,1$ when bit positions start at zero. This is a local maximum pattern, rather than a monotone sequence. The actual coloring rules, target-size losses, and proof excluding homogeneous sets are omitted; the words alone do not constitute a stepping-up theorem.

Research snapshot, checked 11 October 2026. The April 2026 preprint Du, Hu, Liu, and Wang, A double-exponential lower bound for r4(5,n) reports

$$ R_4(5,n)\ge2^{2^{c n^{1/7}}} $$

for an absolute positive constant $c$. This is an off-diagonal theorem reported in a preprint, with uniformity 4 and one target fixed at 5. It should not be presented as an exact value, a best-current-constant claim, or a result determining the two-color diagonal triple number $R_3(s)$. Older descriptions of this off-diagonal tower question as unresolved must be checked against the newer literature. No resolution of the diagonal problem is inferred here.

Exercise. On the four-set $\{1,2,3,5\}$ in the five-vertex construction, determine the four triple colors. Hint: its omitted vertex is 4. Solution: 125 and 123 are red, from complementary pairs 34 and 45; 135 and 235 are blue, from 24 and 14. Again the split is two red, two blue.

Design a Ramsey construction and trace an unavoidable configuration

This investigation connects three kinds of evidence: an avoiding construction, a universal proof, and an exhaustive finite search. Use named red and blue colors throughout, so swapping them produces a different labeled coloring. The optional hypergraph task changes which subsets are colored and which complete configuration is sought; it does not merely replace a graph triangle's name.

Warm-up solution. Each color graph in the five-vertex construction is a 5-cycle, so neither contains a triangle. The 12 interval progressions are:

Digit strings in this table denote the ordered positions of a progression. Every listed triple contains both colors in RRBBRRBB. This list is exhaustive because a positive difference must satisfy $1+2d\le8$.

Universal solution. A sixth vertex has five incident edges, so at least three have the same color. An internal edge of that color completes a monochromatic triangle with the sixth vertex; if none exists, the three neighbors form a triangle of the other color. This recovers the complete upper-bound proof of $R(3,3)=6$ and applies regardless of the original five-vertex coloring.

Explicit trace solution. With vertex 6 red-adjacent to $1,2,3$, the red triangles are 126 and 236. The third pair among those neighbors, 13, is blue, so 136 is not red. The blue neighbors of 6 are 4 and 5, but 45 is red, so no blue triangle uses 6. No old triangle was monochromatic, giving exactly two in total. Appending R to the interval creates 159, and appending B creates 789.

Enumeration solution and a structural check. Exactly 12 of the 1024 labeled two-colorings of $K_5$ avoid monochromatic triangles; none of the 32768 colorings of $K_6$ does. The first number can also be proved without a computer. In any avoiding coloring on five vertices, neither color degree can exceed two, by the same three-neighbor argument. Since the two degrees sum to four, both equal two at each vertex. Each color graph must therefore be a 5-cycle, since a triangle is forbidden. There are $5!/(2\cdot5)=12$ undirected cycles on five labeled vertices, and choosing the red one determines the coloring.

For the graph census, order the pairs lexicographically and represent their colors by bits. For each three-vertex set, inspect its three corresponding bits, rejecting a coloring if they are all zero or all one. This checks ten triangle sets on five vertices and twenty on six. For interval strings, append colors recursively and test only the progressions ending at the new position. The resulting avoiding-string counts for lengths 8 and 9 are 6 and 0; the earlier prefix table supplies each terminal witness.

Optional hypergraph solution. The complement-pair coloring assigns five triples red and five blue. Every four-set contains exactly two red and two blue triples, as proved in Section 21.10. Exhausting all 1024 triple colorings on five vertices finds 512 with no monochromatic tetrahedron. That finite count concerns uniformity 3; it supplies no exact general formula for $R_3(s)$. The contrast between zero graph avoiders on six vertices and surviving triple avoiders on five illustrates how changing the colored subsets changes the problem.

Application to relational data. Suppose every pair of objects is classified into one of two relationship types. Among any six objects, Ramsey's theorem guarantees a triple whose three pair relations all have the same type. It does not guarantee which type occurs, and the two categories need not represent friendship or conflict. For example, an analyst could classify measured similarities as above or below a chosen threshold. The theorem guarantees a uniform pair pattern, while the threshold's meaning and any practical value of that pattern require domain knowledge. If classifications are attached to triples instead, a homogeneous four-object pattern requires four triple labels, and the hypergraph formulation is the appropriate one.

Optional extension. Experiment with three graph-edge colors or with longer interval progressions. Report the largest avoiding construction you actually found, and give a witness for every claimed success. A random search that fails to find an avoider supplies no universal upper bound. To certify an upper bound computationally, the search must exhaust the relevant coloring space or supply a complete verifiable certificate. Research follow-ups can examine the two dated primary preprints cited above, keeping their exact parameter regimes distinct from the elementary finite tasks.