Topological Methods in Combinatorics

Topological combinatorics uses tools from algebraic topology to prove combinatorial results that resist purely combinatorial proofs. The Borsuk-Ulam theorem and its generalizations are the primary engines of this approach.

The Borsuk-Ulam Framework

Definition6.8Borsuk-Ulam Theorem

For every continuous map $f: S^n \to \mathbb{R}^n$ from the $n$ -sphere to $\mathbb{R}^n$ , there exists a point $x \in S^n$ such that $f(x) = f(-x)$ . Equivalently, there is no continuous antipodal map $S^n \to S^{n-1}$ .

Definition6.9$\mathbb{Z}_2$-Index

A free $\mathbb{Z}_2$ -space is a topological space $X$ with a continuous involution $\nu: X \to X$ having no fixed points. The $\mathbb{Z}_2$ -index $\operatorname{ind}(X)$ is the minimum $n$ such that there exists a $\mathbb{Z}_2$ -equivariant continuous map $X \to S^n$ . The Borsuk-Ulam theorem states $\operatorname{ind}(S^n) = n$ .

Kneser's Conjecture

ExampleLovász's Proof of Kneser's Conjecture

Kneser's conjecture (1955, proved by Lovász 1978): The chromatic number of the Kneser graph $K(n, k)$ equals $n - 2k + 2$ . Lovász's proof constructs a simplicial complex (the neighborhood complex $\mathcal{N}(G)$ ) and shows its $\mathbb{Z}_2$ -index is at least $n - 2k$ , which via the Borsuk-Ulam theorem forces $\chi(K(n,k)) \geq n - 2k + 2$ .

RemarkNeighborhood Complex

The neighborhood complex $\mathcal{N}(G)$ of a graph $G$ is the simplicial complex whose simplices are subsets of $V(G)$ that have a common neighbor. Lovász showed that if $\mathcal{N}(G)$ is $(k-1)$ -connected, then $\chi(G) \geq k + 2$ . This connectivity condition is verified for Kneser graphs using topological arguments.

Ham Sandwich and Fair Division

Definition6.10Ham Sandwich Theorem

Given $n$ measurable sets (masses) in $\mathbb{R}^n$ , there exists a single hyperplane that simultaneously bisects each of the $n$ masses. This is a direct consequence of the Borsuk-Ulam theorem applied to the map sending each direction to the hyperplane bisecting the first $n-1$ masses.

ExampleNecklace Splitting Theorem

A necklace has $kn$ beads of $n$ colors ( $k$ beads of each color). It can be fairly divided among $k$ thieves using at most $(k-1)n$ cuts and distributing the resulting intervals among the $k$ thieves so that each gets exactly one bead of each color. The case $k = 2$ follows from the Borsuk-Ulam theorem.

Connectivity and Combinatorics

Definition6.11Topological Connectivity

A simplicial complex $\Delta$ is $k$ -connected if $\pi_i(\|\Delta\|) = 0$ for $i \leq k$ , where $\|\Delta\|$ is the geometric realization. For combinatorial applications, $k$ -connectivity of certain complexes (like the matching complex, chessboard complex, or partition lattice) translates into bounds on chromatic numbers, matching sizes, and other graph parameters.

RemarkThe Topological Tverberg Theorem

The topological Tverberg theorem states: every continuous map $f: \Delta^{(r-1)(d+1)} \to \mathbb{R}^d$ maps $r$ pairwise disjoint faces to a common point, provided $r$ is a prime power. This generalizes Radon's theorem and has deep connections to both topology and combinatorics. For non-prime-power $r$ , counterexamples exist (Frick, 2015).