Ramsey Theory & Extremal Graphs
Ramsey Theory & Extremal Graphs
Ramsey theory asserts that complete disorder is impossible: any large enough structure must contain a prescribed pattern. The Ramsey number $R(s,t)$ is the minimum $n$ such that any 2-coloring of $K_n$'s edges contains a red $K_s$ or a blue $K_t$. Turán's theorem gives the maximum number of edges in a $K_{k+1}$-free graph: the Turán graph $T(n,k)$. These extremal results connect graph theory to combinatorics, number theory, and logic.
Ramsey Numbers
$R(s,t)$ is the minimum $n$ with: every red-blue edge-coloring of $K_n$ contains a red $K_s$ or blue $K_t$. Ramsey's theorem (1930): $R(s,t)$ is finite for all $s,t\geq 2$. Bounds: $R(s,t)\leq\binom{s+t-2}{s-1}$ (greedy/double counting); probabilistic lower bound (Erdős 1947): $R(s,s)>\frac{\sqrt{2}}{e}s\cdot 2^{s/2}$ (random 2-coloring). Known values: $R(3,3)=6$; $R(4,4)=18$; $R(5,5)$ unknown (between 43 and 48).
Turán's Theorem
The Turán graph $T(n,r)$ is the complete $r$-partite graph on $n$ vertices with part sizes as equal as possible. Turán's theorem: $T(n,r)$ is the unique $K_{r+1}$-free graph on $n$ vertices with the maximum number of edges, equal to $t(n,r)=\left(1-\frac{1}{r}\right)\frac{n^2}{2}\cdot(1-o(1))$. Exactly: $t(n,r)=\frac{(r-1)n^2}{2r}$ for $r|n$. Corollary: every graph with $m>t(n,r)$ edges contains $K_{r+1}$.
Example 1
Prove $R(3,3)=6$: any 2-coloring of $K_6$ contains a monochromatic $K_3$.
Solution: Existence ($R(3,3)\leq 6$): pick vertex $v$, degree 5 in $K_6$. By pigeonhole, at least 3 edges to $v$ are the same color (say red). Let $\{u_1,u_2,u_3\}$ be red neighbors. If any edge $(u_i,u_j)$ is red: red $K_3$ with $v$. If all $(u_i,u_j)$ are blue: blue $K_3$ among $u_1,u_2,u_3$. ✓. Sharpness ($R(3,3)>5$): color $K_5$ as a 5-cycle (pentagon) and its complement (pentagram) — no monochromatic triangle. Both are triangle-free.
Example 2
State Turán's theorem and verify it for $K_3$-free graphs.
Solution: Turán: maximum edges in $K_3$-free graph on $n$ vertices is $t(n,2)=\lfloor n^2/4\rfloor$, achieved by $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ (complete bipartite). For $n=4$: $t(4,2)=4$; $K_{2,2}$ has 4 edges and is triangle-free. Any $K_3$-free graph with 5 edges on 4 vertices would need 5 edges (max is $\binom{4}{2}=6$); but $K_4$ has a triangle. Turán says $\leq 4$.
Practice
- Prove the upper bound $R(s,t)\leq R(s-1,t)+R(s,t-1)$ using the greedy argument.
- Apply the probabilistic method to show $R(k,k)>2^{k/2}$.
- Show Turán's theorem implies: if $G$ has $n$ vertices and $m>n^2/4$ edges, then $G$ contains a triangle.
- Describe the Zarankiewicz problem $z(n;s,t)$ and state the Kővári–Sós–Turán theorem.
Show Answer Key
1. Color each edge of $K_{R(s-1,t)+R(s,t-1)}$ red/blue. Pick vertex $v$. It has $R(s-1,t)+R(s,t-1)-1$ neighbors. By pigeonhole, $v$ has $\ge R(s-1,t)$ red neighbors or $\ge R(s,t-1)$ blue neighbors. In the first case, those red neighbors contain a red $K_{s-1}$ or blue $K_t$ by induction; adding $v$ completes a red $K_s$ or we already have blue $K_t$. Similarly for the second case.
2. 2-color edges of $K_n$ randomly (each edge red w.p. 1/2). $P(\text{monochromatic }K_k)\le\binom{n}{k}2^{1-\binom{k}{2}}$. For this $<1$: need $n<2^{k/2}$ (for large $k$). So there exists a 2-coloring with no monochromatic $K_k$ when $n\le2^{k/2}$, i.e., $R(k,k)>2^{k/2}$.
3. Turán's theorem: $\text{ex}(n,K_{r+1})=\left(1-\frac{1}{r}\right)\frac{n^2}{2}$. For triangles ($r=2$): $\text{ex}(n,K_3)=n^2/4$. So if $m>n^2/4$, $G$ must contain a triangle.
4. The Zarankiewicz problem asks for the maximum edges in a bipartite graph on $(n,n)$ vertices with no $K_{s,t}$ subgraph. The Kővári–Sós–Turán theorem gives $z(n;s,t)\le\frac{1}{2}(1+(4(t-1)n)^{1/2})\cdot n^{1-1/s}+\frac{s-1}{2}n$, approximately $O(n^{2-1/s})$.