The chromatic number of cube-like graphs

-
Maya Sankar, IAS
Fine Hall 322

This seminar is open to all eligible participants regardless of identity. 

The chromatic number of a graph is the minimum number of colors needed to color the vertices so that no two vertices connected by an edge receive the same color. A Cayley graph G is a highly symmetric graph whose vertex set is a finite group Gamma. A rather surprising theorem, due to Payan, shows that, if Gamma is (Z/2Z)^n, then G cannot have chromatic number exactly 3. (In other words, if G is 3-colorable then G is also 2-colorable.) I'll show you a new elementary proof of Payan's theorem, and tell you about some topological combinatorics along the way.