Ramsey Theory on Graphs and Hypergraphs

Graph Ramsey theory studies the Ramsey numbers for specific graph classes beyond complete graphs. These problems often require sophisticated probabilistic, algebraic, and analytic techniques.

Graph Ramsey Numbers

Definition5.8Graph Ramsey Number

For graphs $G$ and $H$ , the Ramsey number $R(G, H)$ is the smallest $n$ such that every 2-coloring of $E(K_n)$ contains a red copy of $G$ or a blue copy of $H$ . When $G = H$ , we write $R(G) = R(G, G)$ .

Definition5.9Ramsey Multiplicity

The Ramsey multiplicity $M(G, n)$ counts the minimum number of monochromatic copies of $G$ over all 2-colorings of $K_n$ . For the complete graph $K_3$ , Goodman's formula gives $M(K_3, n) = n(n-1)(n-3)/24 + O(n^2)$ for even $n$ .

Linear Ramsey Numbers

ExamplePath and Cycle Ramsey Numbers

For paths, $R(P_m, P_n) = m + \lfloor n/2 \rfloor - 1$ for $m \geq n \geq 2$ . For cycles, $R(C_m, C_n) = 2m - 1$ when $m \geq n \geq 3$ and $m$ is odd (and slightly different when both are even). These exact values contrast sharply with the difficulty of determining $R(K_n, K_n)$ .

RemarkBurr-Erdos Conjecture (Resolved)

A graph $G$ is $d$ -degenerate if every subgraph has a vertex of degree at most $d$ . The Burr-Erdos conjecture, proved by Lee in 2017, states that $R(G) \leq c_d \cdot |V(G)|$ for every $d$ -degenerate graph $G$ , where $c_d$ depends only on $d$ . This shows that sparse graphs have linear Ramsey numbers.

Hypergraph Ramsey Theory

Definition5.10Hypergraph Ramsey Number

The $k$ -uniform hypergraph Ramsey number $R_k(s, t)$ is the smallest $n$ such that every 2-coloring of $\binom{[n]}{k}$ contains a red set of size $s$ (all $k$ -subsets red) or a blue set of size $t$ . The classical Ramsey number $R(s, t)$ is $R_2(s, t)$ .

ExampleTower-Type Growth

For $k \geq 3$ , the hypergraph Ramsey numbers $R_k(n, n)$ grow as a tower of exponentials of height $k - 1$ . Specifically, Erdos and Rado showed: $\operatorname{tow}_{k-1}(cn^2) \leq R_k(n, n) \leq \operatorname{tow}_{k-1}(Cn^2),$ where $\operatorname{tow}_h(x)$ denotes a tower of 2s of height $h$ with $x$ on top. This tower growth is sharp.

RemarkStepping-Up Lemma

The Erdos-Rado stepping-up lemma derives bounds for $R_{k+1}$ from bounds for $R_k$ by encoding $k$ -colorings into $(k+1)$ -colorings via ordinal arguments. This technique is responsible for the tower-type behavior of hypergraph Ramsey numbers and has been refined by Conlon, Fox, and Sudakov.

Applications of Ramsey Theory

ExampleErdos-Szekeres Theorem

A celebrated application of Ramsey theory: among any $\binom{2n-2}{n-1} + 1$ points in general position in the plane, there exist $n$ points forming a convex polygon. This follows from $R(n, n)$ applied to a suitable 2-coloring of triples. The Erdos-Szekeres conjecture on the tight bound $2^{n-2} + 1$ was recently proved by Suk for large $n$ .