Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles

Fix $r\ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht.

Our proof relies on a graph-theoretic analogue of homotopy equivalence, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex, and opens many further interesting questions.