Extremal Combinatorics

Extremal Problems

Extremal combinatorics: how large or small can an object with given properties be?

Turán's Theorem: The maximum number of edges in a $K_{r+1}$-free graph on $n$ vertices: $e \leq (1 - 1/r) \cdot n^2/2$. Achieved on the complete $r$-partite Turán graph $T(n, r)$.

Erdős's Distinct Distances Problem: $n$ points in the plane determine at least $c\sqrt{n}$ distinct distances.

The Pigeonhole Principle (Box Principle)

If $n$ objects are placed into $m$ boxes and $n > m$, then some box contains at least 2 objects.

Generalization: if $n > km$, then some box contains at least $k+1$ objects.

Application: among 13 people, two were born in the same month. Among 367 people, two were born on the same day. Problem of 5 points in the unit square: two are at a distance $\leq \sqrt{2}/2$.

We divide the square into 4 parts; if $n=5$ points $\rightarrow$ at least 2 in one part $\rightarrow$ distance $\leq$ diagonal of the part $= \sqrt{2}/2$.

Ramsey and Gelfand Theorems

Van der Waerden: For any $k$ and $r$, there exists $N$ such that for any $r$-coloring of ${1,\dots,N}$ there is a monochromatic $k$-term arithmetic progression.

Khinchin's Theorem: For any two-coloring of the natural numbers, a monochromatic set contains infinitely many $k$-term arithmetic progressions.

These theorems show: in large structures, regular patterns inevitably arise.

The Green–Tao Theorem and Primes in AP

In 2004, Ben Green and Terence Tao proved: prime numbers contain arithmetic progressions of any length. The proof combines Szemerédi's regularity method (for structural arguments) and the theory of prime numbers (for density estimates of pseudorandom sets). This is one of the greatest results of 21st-century mathematics.

Van der Waerden Numbers and Computational Complexity: Calculating $W(2;k)$ is a problem with phenomenally complex behavior. $W(2;3)=9$ (three colors on eight numbers without a monochromatic AP-3). $W(2;4)=35$, $W(2;5)=178$, $W(2;6)=1132$. The growth is extremely rapid: Gowers' upper bounds have the form of tower functions (tetration like $2^{2^{...^2}}$). The function $W(r;k)$ itself is primitive recursive and computable, but practically unattainable for large $k$.

Ultrametrics and Metric Ramsey Results

Ultrafilters are used in proofs of infinite versions of Ramsey’s theorem: compactness of the ultrafilter space (Tychonoff’s theorem) gives elegant non-finite proofs. For metric spaces there are analogs of Ramsey’s theorem: in any sufficiently large finite metric space there is a large approximately equidistant subset. Applications in computer vision (invariants to deformations) and databases (metric clustering).

Polychromatic Ramsey Numbers

Multicolored Ramsey Numbers: Unlike the two-colored case, multicolored variants are significantly more complicated. $R(3,3,3) = 17$: for any edge-coloring of $K_{17}$ with three colors there is a monochromatic triangle. The value $R(3,3,3,3)$ is unknown. Dimensional Ramsey Numbers: For which $n$-dimensional space does every coloring of the points contain a monochromatic regular multidimensional body? This is an active area of research.

Combinatorial Games and the Hex Theorem

The game of Hex on an $n \times n$ board—the first player (connecting the left and right edges) wins with optimal play. Proof by strategy stealing: if the second player had a winning strategy, the first could “steal” it. Existence of a winning strategy for the first player—but constructing it explicitly for large $n$ is an open problem. Hex is related to Brouwer’s fixed point theorem: existence of a winning path is equivalent to a fixed point for a continuous mapping of the simplex.

Game Theory and Combinatorial Games: Grundy Numbers

Grundy Numbers (Nimbers): $G(\text{position}) = \mathrm{mex}{G(p') : p'$ is a next position$}$. $\mathrm{mex}$ is the minimal excluded non-negative integer. Sprague–Grundy Theorem: any combinatorial game is equivalent to a Nim heap $G(\text{position})$. Sum of games: $G(G_1 + G_2) = G_1 \oplus G_2$ (XOR). Applications: Nim, Hackenbush, Topping.

Alphabetic Games and Codes

Guessing Game: binary search—strategy for minimal number of questions. Connection to codes: the optimal question tree is the optimal prefix code. Ulam's Game (20 Questions with Lies): allow $k$ liars—optimal strategy via error-correcting codes. Browser’s Combinatorial Game: a winning strategy is equivalent to the chromatic number of a certain graph.

Deterministic Cellular Automata

Cellular Automata (CA): discrete model of computation. A row of cells, each in a state from a finite alphabet. Transition: new state $=$ $f$(states of neighbors). Rule 30 (Wolfram): from simple rules—complex chaotic behavior. Rule 110 is a Turing-complete CA (proved by Matthew Cook, 1994). Conway’s “Game of Life” is a two-dimensional CA: complex structures (gliders, oscillators), Turing-complete.

The Monotone Function Theorem and Probabilistic Combinatorics

A monotone property of a graph $G$ (adding edges does not destroy the property, e.g. containing a clique) has a threshold function $p^*(n)$. Friedgut–Kahn Theorem: if the property is “symmetric” (invariant under automorphisms of $K_n$), then the threshold is sharp. This explains “thresholds” in $G(n,p)$—the property appears suddenly. Fuzzy thresholds: examples exist for non-symmetric properties.

Ramsey’s Theorem for Hypergraphs

Generalization: for $k$-uniform hypergraphs on $R^{(k)}(s,t)$ vertices, any two-coloring of $k$-subsets contains a monochromatic $s$- or $t$-subset. Ramsey numbers for hypergraphs grow doubly exponentially. $R^{(3)}(4,4)$ is not known exactly. Graham–Rothschild theorem: combinatorial cubes contain monochromatic affine subspaces—a quantitative version of Hindman’s theorem.

Numerical Example: Ramsey Number $R(3,3)=6$

Problem: Prove $R(3,3) \leq 6$: any two-color edge-coloring of $K_6$ contains a monochromatic triangle.

Step 1: Take an arbitrary vertex $v$ in $K_6$. It is connected to 5 other vertices by edges in two colors.

Step 2: By the pigeonhole principle: among the 5 edges at least $\lceil 5/2 \rceil=3$ are of one color. Suppose $v$ is connected by red edges to vertices $a, b, c$.

Step 3: Look at the triangle ${a, b, c}$. If edge $ab$, $bc$ or $ac$ is red $\rightarrow$ red triangle with $v$. If all three edges are blue $\rightarrow$ ${a, b, c}$ themselves form a blue triangle.

Step 4: Both cases yield a monochromatic triangle. Lower bound: $K_5$ with “pentagon” coloring (5 cycle edges = red, 5 diagonals = blue) does not contain a monochromatic triangle $\rightarrow R(3,3) > 5$. Therefore $R(3,3) = 6$. ✓