An introduction to topological combinatorics

The chromatic number of a graph is the number of vertex colors needed so that adjacent vertices have different colors. In 1955, Kneser made a conjecture about the chromatic number of a certain family of graphs (now called Kneser graphs). This conjecture remained unproven for 23 years until Lovász gave a topological proof in 1978. This marked the beginning of a new field, topological combinatorics, in which tools from algebraic topology are used to solve problems in combinatorics. In the first part of my talk, I will share a proof of Kneser’s conjecture.

The second part of my talk will fast-forward to the present day. The Gromov-Hausdorff distance is a notion of dissimilarity between two metric spaces. It is an important tool in geometry, but notoriously difficult to compute. I will show how topological combinatorics provides (potentially tight) lower bounds on the Gromov-Hausdorff distance between unit spheres of different dimensions. This is joint work in a polymath-style project with many people who are currently or formerly at Colorado State, Ohio State, Carnegie Mellon, or Freie Universität Berlin.