Ramsey Theory

Fix a vertex $v$. Partition the other $m+n-1$ vertices into the red neighbours $A$ of $v$ and the blue neighbours $B$ of $v$. If $\mathrm{\mid }A\mathrm{\mid }\ge m$, restrict to an $m$-element subset of $A$ and apply $m\to (s-1,t{)}^2$; if $\mathrm{\mid }A\mathrm{\mid }<m$, then $\mathrm{\mid }B\mathrm{\mid }\ge n$ by the finite sum rule, so restrict to an $n$-element subset of $B$ and apply $n\to (s,t-1{)}^2$.

In the first case, a red $(s-1)$-set in $A$ becomes a red $s$-set after adjoining $v$, while a blue $t$-set already works. In the second case, a blue $(t-1)$-set in $B$ becomes a blue $t$-set after adjoining $v$, while a red $s$-set already works. Hence every colouring has one of the alternatives in [F1], so $m+n\to (s,t{)}^2$.

If $s=1$ or $t=1$, every nonempty vertex set contains the required one-vertex set in the corresponding colour convention, and the displayed binomial coefficient is $1$.

Assume $s,t\ge 2$ and that the formula holds whenever the sum of the two positive parameters is smaller than $s+t$. Then $\left(\genfrac{}{}{0px}{}{s+t-3}{s-2}\right)\to (s-1,t{)}^2$ and $\left(\genfrac{}{}{0px}{}{s+t-3}{s-1}\right)\to (s,t-1{)}^2$ by the induction hypothesis.

Apply [L1] to the two witnesses in step 1.2 and use [L2] to identify their sum as $\left(\genfrac{}{}{0px}{}{s+t-2}{s-1}\right)$. This gives the displayed arrow for $(s,t)$.

The base faces and the induction step cover all positive $s,t$, so the explicit binomial witness works universally.

The numbers $R(s-1,t)$ and $R(s,t-1)$ satisfy the two hypotheses of [L1]. Hence their sum arrows to $(s,t)$, and leastness in the definition of $R(s,t)$ gives the recursion inequality.

The finite binomial theorem gives $R(k,k)\le \left(\genfrac{}{}{0px}{}{2k-2}{k-1}\right)$. In [L2] put $x=y=1$ and $n=2k-2$; every summand is nonnegative, so the single central coefficient is at most their sum $2^{2k-2}$.

At a fixed vertex $v$ of $K_6$, at least three of its five incident edges have one colour by [L1]. Call their other endpoints $a,b,c$ and suppose that colour is red. If one of $ab,bc,ca$ is red it closes a red triangle with $v$; if none is red, then $a,b,c$ form a blue triangle. The same argument with the colour names exchanged proves $6\to (3,3{)}^2$.

On five cyclically ordered vertices, colour the five cycle edges red and the remaining five edges blue. The red graph is a $5$-cycle and has no triangle; the blue graph is also a $5$-cycle, in the order obtained by stepping two places at a time, and has no triangle. Thus $5\to ̸(3,3{)}^2$.

Step 1.1 gives $R(3,3)\le 6$ and step 1.2 gives $R(3,3)>5$. Since $R(3,3)$ is a natural number, it equals $6$.

There are $\left(\genfrac{}{}{0px}{}{N}{2}\right)$ edges in $K_N$, and [L1] therefore counts exactly $2^{\left(\genfrac{}{}{0px}{}{N}{2}\right)}$ red-blue edge colourings.

For a fixed $k$-vertex set, exactly $2\cdot 2^{\left(\genfrac{}{}{0px}{}{N}{2}\right)-\left(\genfrac{}{}{0px}{}{k}{2}\right)}$ colourings make all its edges monochromatic. Summing these finite bad sets over the $\left(\genfrac{}{}{0px}{}{N}{k}\right)$ choices, with overlaps allowed, shows that a colouring with no monochromatic $k$-set exists whenever $2\left(\genfrac{}{}{0px}{}{N}{k}\right)2^{-\left(\genfrac{}{}{0px}{}{k}{2}\right)}<1$.

If $N<k$, then $\left(\genfrac{}{}{0px}{}{N}{k}\right)=0$ by the definition of the binomial coefficient. If $k\le N$, [L2] gives $\left(\genfrac{}{}{0px}{}{N}{k}\right)k!=N^{\underset{‾}{k}}\le N^k$, so again $\left(\genfrac{}{}{0px}{}{N}{k}\right)\le N^k\mathrm{/}k!$. Since $N\le 2^{k\mathrm{/}2}$, the left side in step 2.1 is therefore at most $2^{1+k\mathrm{/}2}\mathrm{/}k!$ in either case. At $k=3$ this is $2^{5\mathrm{/}2}\mathrm{/}6<1$; thereafter the ratio of the bound for $k+1$ to that for $k$ is $\sqrt{2}\mathrm{/}(k+1)<1$. Hence the strict inequality holds for every $k\ge 3$.

Step 2.1 supplies a colouring on $N$ vertices with no monochromatic $k$-set, so $R(k,k)>N$. As $R(k,k)$ is an integer and $N=\lfloor 2^{k\mathrm{/}2}\rfloor$, [L3] implies $R(k,k)\ge N+1>2^{k\mathrm{/}2}$.

If $r=1$ or $c=1$, any sufficiently large finite set works. For $k=1$, $N=c(r-1)+1$ works by finite pigeonhole. For $k=2$, repeatedly group one colour against all remaining colours and apply [L1]; induction on $c$ gives a finite multicolour graph witness for every target $r$.

Assume $k\ge 3$ and that the theorem is known for $(k-1)$-subsets with every finite colour and target parameter. Put $M=c(r-1)+1$. Choose finite reservoir sizes backwards by $q_M=1$ and, for $i<M$, let $q_i$ be one more than a $(k-1)$-uniform Ramsey witness for target $q_{i+1}$ and $c$ colours, which exists by the induction hypothesis.

Starting with a $q_0$-element set, choose its least vertex $x_0$. Colour each $(k-1)$-subset $A$ of the remaining reservoir by the colour of $A\cup \{x_0\}$, and restrict to a homogeneous $q_1$-element reservoir. Repeat. After $M$ stages there are vertices $x_0,\dots ,x_{M-1}$ and colours $d_0,\dots ,d_{M-1}$ such that every $k$-set of chosen vertices whose least member is $x_i$ has colour $d_i$.

Finite pigeonhole gives indices $i_1<\cdots <i_r$ for which $d_{i_1}=\cdots =d_{i_r}$. Every $k$-subset of $\{x_{i_1},\dots ,x_{i_r}\}$ has least element $x_{i_j}$ for some $j$, hence has this common colour by step 2.1. This is a monochromatic $r$-set.

The bases and the step from $(k-1)$ to $k$ prove the assertion for every positive $k,c,r$.

Call a node viable if it has descendants at arbitrarily high levels. The root is viable: if each of its finitely many successors had descendants only up to some level, the maximum of those finitely many bounds would bound the whole tree, contrary to the existence of a node at every level.

Every viable node has a viable immediate successor. Otherwise all its finitely many successors would have bounded descendant height, and the maximum of their bounds would contradict viability. The viable successor labels form a nonempty set of naturals, so [L1] gives a unique least one.

On the set of viable nodes, send each node to its least viable successor from step 2.1. Apply [L2] from the root. Every finite initial segment produced is a node of $T$, and at stage $n$ it has length $n$. Thus the recursive sequence is an infinite branch.

Suppose every fibre $c^{-1}(\{i\})$, for $i\in C$, is finite. These fibres are pairwise disjoint and their union is $\mathbb{N}$.

Iterating [L1] over the finite set $C$ makes their union finite. This contradicts the infinitude of $\mathbb{N}$, so at least one fibre is not finite. That fibre is a subset of $\mathbb{N}$, and [L2] therefore makes it countably infinite.

For $k=1$, [L1] is exactly the assertion. The one-colour case is immediate for every $k$.

Assume the result for $k$ and consider a colouring of $(k+1)$-subsets. Whenever the induction hypothesis produces an infinite homogeneous subset of a set of naturals, make one output canonical as follows. Among the $k$-subsets whose colours admit an infinite homogeneous set, choose the lexicographically least subset and use its colour. Then recursively choose the least next natural that extends the current finite prefix to some infinite homogeneous set of that colour. The candidate sets are nonempty, so [L2] and natural recursion define a unique increasing enumeration without ordering the arbitrary colour set and without choice.

Set $R_0=\mathbb{N}$. Given the infinite reservoir $R_n$, let $x_n$ be its least element and transfer the colouring $A\mapsto c(A\cup \{x_n\})$ on $[R_n\setminus \{x_n\}{]}^k$ along that set's unique increasing enumeration from $\mathbb{N}$. Apply the induction hypothesis and the canonical rule of step 1.2, then transfer back to obtain an infinite homogeneous reservoir $R_{n+1}\subseteq R_n\setminus \{x_n\}$; let $d_n$ be its colour. Natural recursion performs this construction for all $n$.

Apply [L1] to $n\mapsto d_n$. Let $j$ be the least index whose colour class is infinite, and put $I=\{n:d_n=d_j\}$. If $i_0<\cdots <i_k$ lie in $I$, then $x_{i_1},\dots ,x_{i_k}\in R_{i_0+1}$ by nestedness, so $c(\{x_{i_0},\dots ,x_{i_k}\})=d_{i_0}=d_j$. Hence $\{x_i:i\in I\}$ is infinite and monochromatic.

The base and the induction step establish the theorem for every positive $k$, and every selection made in the construction was the least member of a nonempty subset of $\mathbb{N}$.

Define a colouring of $[\mathbb{N}{]}^k$ by $A\mapsto c(j[A])$. Injectivity in [F1] makes $j[A]$ a $k$-element set, so [L1] gives an infinite homogeneous $H\subseteq \mathbb{N}$.

By [F1], the restriction $j{\mathrm{\mid }}_H$ is a bijection from $H$ to $j[H]$, so $j[H]$ is infinite. The pullback definition shows every $k$-subset of $j[H]$ has the same $c$-colour.

Suppose no finite witness exists. Form a tree whose level-$N$ nodes are the bad colourings of $[\{0,\dots ,N-1\}{]}^k$, ordered by extension. Restricting a bad colouring remains bad, every level is nonempty by the supposition, and every node has only finitely many one-level extensions. Order those extensions lexicographically by their finite colour tables.

By [L1] the tree has a coherent branch. The union of its compatible finite functions is a well-defined $c$-colouring of $[\mathbb{N}{]}^k$, and every finite restriction on the branch has no monochromatic $r$-set.

Apply [L2] to the union colouring and take the first $r$ elements of its infinite monochromatic set. They lie below some $N$, so they form a monochromatic $r$-set in the level-$N$ branch node, contradicting its badness. Therefore a finite witness exists.

Colour each $i<j<k<l$ according as $c(ij)=c(kl)$. By [L1], thin to an infinite set on which this answer is constant. If it is yes, any two pairs can be compared through a third pair lying to their right, so $c$ is constant. Henceforth the answer is no: separated pairs have different colours.

On the set from step 1.1, thin by [L1] for the relation $c(il)=c(jk)$ on $i<j<k<l$. The constant answer cannot be yes: on six ordered points it would give $c(x_2{x}_3)=c(x_1{x}_6)=c(x_4{x}_5)$, contradicting step 1.1. Thus every such nested pair has different colours.

Thin again for the relation $c(ik)=c(jl)$. A constant yes answer on six points similarly gives $c(x_1{x}_3)=c(x_2{x}_5)=c(x_4{x}_6)$, again contradicting step 1.1. Thus crossing pairs have different colours.

Successively thin triples so that each of the relations $c(ij)=c(ik)$, $c(ik)=c(jk)$ and $c(ij)=c(jk)$ has a constant truth value for $i<j<k$. The last relation cannot be always true, since four points would then make two separated pairs equal by transitivity.

If both of the first two relations were always true, the last would also be true, which step 2.3 excludes. If only the first is always true, equality of colours is exactly equality of left endpoints; if only the second is always true, it is exactly equality of right endpoints. The converse implications follow from the corresponding always-true relation, while pairs with different relevant endpoints are covered by steps 1.1, 2.1, and 2.2 and the always-false triple relations.

If both first relations are always false, any two distinct pairs are separated, nested, crossing, or share exactly one endpoint; steps 1.1, 2.1, and 2.2 and the triple relations show their colours differ, so $c$ is injective. Together with the constant case and step 3.1, this yields one of the four canonical forms on an infinite set.

For $r=1$ and $m=2$, the singleton progression $\{1\}$ with chosen difference $1$ is focused at $2$. For $m\ge 3$, apply $V(m-1,k)$ inside the first half of an interval twice as long. Its monochromatic $(m-1)$-term progression has positive difference at most the length of that half, so its next term still lies in the full interval. In either case there is one focused progression.

Assume $r>1$. Take $m=2$ first, where the block construction below has nothing to work with: a $1$-term progression of block indices carries no difference. It is not needed. Among any $k+1$ points two share a colour, and two points $a<b$ of one colour are a monochromatic $2$-term progression with difference $b-a>0$, so $F(2,k,r)=k+1$ and the first alternative always holds. Assume from here that $m\ge 3$, and let $n=F(m,k,r-1)$. Partition a sufficiently long interval into consecutive blocks of length $2n$. By [L1] there are $k^{2n}$ possible block colour vectors. Use $V(m-1,k^{2n})$ on the sequence of block vectors to obtain identically coloured blocks whose indices are $b,b+t,\dots ,b+(m-2)t$.

Apply the induction hypothesis to the first half of the first selected block, an interval of length $n=F(m,k,r-1)$. It gives either a monochromatic $m$-term progression, which finishes, or $r-1$ colour-focused progressions $A_i=\{a_i+j{d}_i:0\le j<m-1\}$ of pairwise distinct colours focused at $f$. Each $A_i$ lies in that first half, so $a_i+(m-2)d_i\le n$ measured from the block start, and $m\ge 3$ makes both $a_i$ and $d_i$ at most $n$; hence $f=a_i+(m-1)d_i\le 2n$ and the focus lies in the block. That is what the block length $2n$ is for, exactly as in step 1.1. For the second alternative define $A_i^{\mathrm{\prime }}=\{a_i+j(d_i+2nt):0\le j<m-1\}$. Its $j$th term occupies the same relative position in block $b+jt$ as the $j$th term of $A_i$ in block $b$, so identical block vectors preserve its colour.

The progressions $A_i^{\mathrm{\prime }}$ are focused at $f+(m-1)2nt$. Since $f$ lies in block $b$ by step 2.1, the point $f+j2nt$ occupies the same relative position in block $b+jt$ as $f$ does in block $b$, so identical block vectors make $f,f+2nt,\dots ,f+(m-2)2nt$ a monochromatic $(m-1)$-term progression, focused at the same point and coloured as $f$ is. If that colour equals the colour of some $A_i$, then $A_i\cup \{f\}=\{a_i+j{d}_i:0\le j\le m-1\}$ is a monochromatic $m$-term progression and the first alternative holds. Otherwise the new progression differs in colour from all $r-1$ of the $A_i^{\mathrm{\prime }}$, which already have pairwise distinct colours, and the second alternative contains $r$ focused progressions of distinct colours.

The base and step prove the focusing assertion for every $1\le r\le k$.