Extremal Graph Theory

Extremal graph theory asks: how many edges can a graph have while avoiding a given subgraph? The answers are surprisingly precise and often achieved by a unique construction.

• **Social network clustering:** networks with bounded triangle counts are studied via Turan numbers
• **Error-correcting codes and expanders:** Ramsey theory connects to codes with given distance parameters
• **Computational geometry:** crossing numbers for point configurations are governed by extremal graph problems

Предварительные знания

• Algebraic Graph Theory

Turan's Theorem and Turan Numbers

Paul Turan formulated his problem in a Budapest internment camp in 1941: a graph on n vertices without a triangle contains at most n^2/4 edges. This result became the foundation of modern extremal combinatorics.

Ramsey Numbers

The Ramsey problem appeared in Frank Ramsey's 1930 paper. For R(3,3)=6: any 2-coloring of K_6 contains a monochromatic triangle. The lower bound for R(5,5) is unknown to within tens: somewhere between 43 and 48.

Key ideas

• **Turan's theorem:** ex(n,K_{r+1}) = (1-1/r)*n^2/2; extremal graph T(n,r) is the balanced complete r-partite graph
• **Mantel's theorem:** ex(n,K_3) = floor(n^2/4); triangle-free maximum is K_{n/2,n/2}
• **Erdos-Stone theorem:** ex(n,H) = (1-1/(chi(H)-1))*n^2/2 + o(n^2); only the chromatic number matters asymptotically