Ramsey Numbers

Ramsey theory studies the emergence of order in large structures. The central theme is that sufficiently large combinatorial objects necessarily contain highly organized substructures, regardless of how disordered the original structure may appear.

Classical Ramsey Numbers

Definition5.1Ramsey Number $R(s,t)$

The Ramsey number $R(s, t)$ is the smallest positive integer $n$ such that every 2-coloring of the edges of $K_n$ (red and blue) contains either a red $K_s$ or a blue $K_t$ . Equivalently, for every graph $G$ on $n$ vertices, either $G$ contains $K_s$ as a subgraph or its complement $\overline{G}$ contains $K_t$ .

Definition5.2Multicolor Ramsey Number

The $k$ -color Ramsey number $R(n_1, n_2, \ldots, n_k)$ is the smallest integer $N$ such that every $k$ -coloring of the edges of $K_N$ contains a monochromatic $K_{n_i}$ in color $i$ for some $i \in \{1, \ldots, k\}$ .

Known Values and Bounds

ExampleSmall Ramsey Numbers

The known exact values include:

$R(3, 3) = 6$ : any 2-coloring of $K_6$ contains a monochromatic triangle.
$R(3, 4) = 9$ , $R(3, 5) = 14$ , $R(4, 4) = 18$ .
$R(4, 5) = 25$ was determined in 1995.
$R(5, 5)$ is unknown; the best bounds are $43 \leq R(5, 5) \leq 48$ .

RemarkExponential Bounds

The Erdos-Szekeres recursive bound gives $R(s, t) \leq \binom{s + t - 2}{s - 1}$ . For the diagonal case, this yields $R(n, n) \leq \binom{2n - 2}{n - 1} \leq \frac{4^{n-1}}{\sqrt{\pi(n - 1/2)}}$ . Erdos's probabilistic lower bound gives $R(n, n) \geq \frac{n}{e\sqrt{2}} \cdot 2^{n/2}$ , and improving either bound significantly remains a major open problem.

Ramsey Theory on Integers

Definition5.3Schur Number

The Schur number $S(r)$ is the largest integer $n$ such that $\{1, 2, \ldots, n\}$ can be $r$ -colored without any monochromatic solution to $x + y = z$ . Equivalently, $S(r) + 1$ is the minimum $N$ such that every $r$ -coloring of $[N]$ contains a monochromatic Schur triple. Known values: $S(1) = 1$ , $S(2) = 4$ , $S(3) = 13$ , $S(4) = 44$ .

ExampleSchur's Theorem for 2 Colors

$S(2) = 4$ : The coloring $\{1, 4\}$ red, $\{2, 3\}$ blue on $[4]$ avoids monochromatic Schur triples. But on $[5]$ , every 2-coloring must produce a monochromatic $\{x, y, x+y\}$ . If $1$ and $2$ get the same color (say red), then $3 = 1 + 2$ must be blue, $4 = 1 + 3$ must be red, and $5 = 2 + 3$ must be red, but $1 + 4 = 5$ are both red.