Mathematical Conversations

A few years ago, I was introduced to a surprising result of Payan stating that certain highly symmetric "cube-like" graphs cannot have chromatic number exactly $3$. (Specifically, his result applies to graphs on vertex set $(\mathbf{Z}/2\mathbf{Z})^d$ for some d that are translation-invariant: every translation $\vec{v} \mapsto \vec{v}+\vec{x}$ of the vertex set is also an automorphism of the graph.)  Payan's theorem is unexpected because one generally shows a graph $H$ either has chromatic number $\leq k$ or $>k$ --- which is equivalent to $H$ being $k$-colorable or not. In comparison, this theorem states a cube-like graph is either $2$-colorable or non-$3$-colorable, which are difficult conditions to compare.

In this talk, I'll tell you a short new proof of Payan's theorem (joint with Mike Krebs). The proof uses topological ideas and applies beyond cube-like graphs --- including to quadrangulations of $\mathbf{RP}^2$ and to translation-invariant graphs on $(\mathbf{Z}/4\mathbf{Z})^d$.