
Neighborhood Complexes, Kneser Graphs, and the Borsuk-Ulam Theorem
Maya Sankar, speaking in the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar, argues for the chromatic number of Kneser graphs using topological methods. The Kneser graph KG(n,k) has as vertices the size-k subsets of a set of n elements, with edges joining disjoint subsets, and Sankar works through several proofs, each resting on the Borsuk-Ulam theorem, that the obvious (n-2k+2)-coloring is optimal. Along the way she introduces the neighborhood complex and the box complex, topological spaces built from a graph, and shows how their properties give lower bounds on chromatic number in general. The talk is framed as a series of vignettes rather than a single linear argument, and is pitched as gentle: no prior algebraic topology is assumed. It runs close to two hours, giving room for the proofs to be developed carefully on the blackboard in the Simonyi Classroom.