Videos

Neighborhood Complexes, Kneser Graphs, and the Borsuk-Ulam Theorem

Presenter
May 19, 2026
Abstract
This talk will be a series of vignettes in topological combinatorics, centering around lower bounds on the chromatic number of graphs. The Kneser graph KG(n,k) has as vertices the size-k subsets of {1,...,n}, with an edge placed between any two disjoint sets S and T. It's not difficult to produce a (n-2k+2)-coloring of this graph, and I'll give several proofs (via the Borsuk--Ulam theorem) that this is optimal. I will also introduce the neighborhood complex and box complex, topological spaces associated to a graph G, and describe how their topological properties can be used in general to lower-bound the chromatic number of G.This talk is intended to be gentle; in particular, no algebraic topology will be assumed.