Codex @codex  0

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

Set $R(1,t)=R(s,1)=1$. For $s,t\ge 2$, let $N=R(s-1,t)+R(s,t-1)$ and fix a vertex $v$ in a red-blue colouring of $K_N$. Among the remaining $N-1$ vertices, either at least $R(s-1,t)$ are red neighbors of $v$, or at least $R(s,t-1)$ are blue neighbors. In the first case their induced colouring gives a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. This proves the Ramsey number recursionInduction on $s+t$, using the boundary values and Pascal's identity, now gives the binomial upper bound for a Ramsey number:In particular this induction proves that the required Ramsey number exists.

Induction with Pascal's identity gives the binomial upper bound for a Ramsey number $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. Thus $R(s)\le \left(\genfrac{}{}{0ex}{}{2s-2}{s-1}\right)\le 4^{s-1}$, proving $R(s)=O(4^s)$.

For the lower bound, take a binomial random graph $G(n,1/2)$. The expected total number of $s$-cliques and independent $s$-sets isFor $n=\lfloor 2^{s/2}/2\rfloor$, this is at most $2^{1-s/2}/s!<1$ for all sufficiently large $s$. Some graph therefore has neither forbidden set, so $R(s)>n$. This proves $R(s)=\Omega (2^{s/2})$ by the probabilistic method.

The binomial upper bound for a Ramsey number gives $R(3,t)\le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)=O(t^2)$. For the triangle-free Ramsey lower bound by alteration, a binomial random graph $G(n,p)$ has expected triangle count $\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$ and expected independent $t$-set count $\left(\genfrac{}{}{0ex}{}{n}{t}\right)(1-p{)}^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Choose a realization whose sum of these counts is at most its expectation. Delete one vertex from each surviving forbidden set, iterating through the originally listed sets. The remaining graph has neither a triangle nor an independent $t$-set. This random alteration method provesFor large $t$, set $n=\lfloor (t/(4\log t){)}^{3/2}\rfloor$ and $p=n^{-2/3}$. The triangle term is at most $n/6$. Using $\left(\genfrac{}{}{0ex}{}{n}{t}\right)\le (en/t{)}^t$ and $1-p\le e^{-p}$, the logarithm of the independent-set term divided by $t$ is at mostwhich tends to $-\infty$. That term is eventually below $1$. Thus $R(3,t)>5n/6-1$ and

A graph Ramsey number $R(s,t)$ is the least $N$ such that every red-blue edge colouring of the complete graph $K_N$ has a red $K_s$ or a blue $K_t$. At a vertex in $K_{R(s-1,t)+R(s,t-1)}$, either at least $R(s-1,t)$ neighbours have red incident edges or at least $R(s,t-1)$ have blue incident edges. In the first case find a red $K_{s-1}$ and adjoin the vertex, or a blue $K_t$; the second case is symmetric. ThusStarting with $R(2,t)=t$ and $R(s,2)=s$, induction gives the binomial upper bound for a Ramsey numberFor the lower construction, partition $2t-2$ vertices into two classes of size $t-1$, colour inside-class edges red and between-class edges blue. Red cliques have at most $t-1$ vertices, and the blue graph is bipartite, so has no odd cycle.

Conversely, a graph without an odd cycle is bipartite: in each connected component colour vertices by the parity of the length of a path from a root; differing path parities would give an odd closed walk, hence an odd cycle. On $2t-1$ vertices one of the two blue bipartition classes has at least $t$ vertices. Every edge within it is red, giving a red $K_t$. Thus $2t-1$ is the exact threshold for this alternative.

The diagonal Ramsey number $R(s)$ is the least positive integer $N$ such that every red-blue edge colouring of the complete graph $K_N$ contains a monochromatic copy of $K_s$.

For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the pigeonhole principle says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. HenceStarting from $R(1,s)=R(r,1)=1$ and using Pascal's identity gives the binomial upper bound for a Ramsey numberThereforewhich proves both existence and the required estimate.

To determine $R(3)$, color a cycle graph $C_5$ red and its complement graph, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\le 6$, and

The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has vertex degree at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a regular graph of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.

Finally, the monochromatic-triangle counting formula gives, for a coloring of $K_6$ with red degrees $d_v$,The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore

We use the Erdős-Rado selection argument. PutStarting with a sufficiently large reservoir, choose vertices $v_1,\dots ,v_m$ in order. After choosing $v_j$, successively halve the remaining reservoir for each $i<j$ so that the colour ofis constant as $x$ ranges over the final reservoir. The total number of halvings is at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, so $2^{\left(\genfrac{}{}{0ex}{}{m}{2}\right)}+m$ initial vertices suffice.

Colour the pair $ij$, for $i<j<m$, by the stabilized colour of $\{v_i,v_j,v_{\ell }\}$ for $\ell >j$. Among $v_1,\dots ,v_{m-1}$, the definition of $R^{(2)}(k-1)$ gives a monochromatic set of $k-1$ vertices. Adjoining $v_m$ gives a monochromatic $k$-set for the original triple colouring. HenceThe binomial upper bound for a Ramsey number gives $R^{(2)}(k-1)<2^{2k}$, so the right-hand side is at mostfor an absolute $C>0$.

The diagonal Ramsey number $R(t)$ is the least positive integer $n$ such that every red-blue colouring of the edges of $K_n$ contains a monochromatic $K_t$.

More generally, let $R(s,t)$ be the least $n$ forcing either a red $K_s$ or a blue $K_t$. We haveAssuming the two smaller numbers exist, colourand choose a vertex $v$. At least $R(s-1,t)$ of its incident edges are red, or at least $R(s,t-1)$ are blue. In the first case, the corresponding neighbourhood contains a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. Thuswhich proves existence by induction.

Pascal's identity then gives the binomial upper bound for a Ramsey numberConsequently, for $t\ge 2$,

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.