Homotopy and the Homomorphism Threshold of Odd Cycles

MaRDI QIDQ6402179zbMATH OpenFDO

Authors Maya Sankar

Publication date 15 June 2022

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: Consider a family $mathcalF$ of $C_{2r+1}$-free graphs, where $rgeq2$. Suppose that each graph in $mathcalF$ has minimum degree linear in its number of vertices. Thomassen showed that such a family has bounded chromatic number, or, equivalently, that all graphs in $mathcalF$ are homomorphic to a complete graph of bounded size. Considering instead homomorphic images which are themselves $C_{2r+1}$-free, 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 odd cycles of length at least 5 and answers a question of Ebsen and Schacht. Our proof introduces a new technique to describe the topological structure of a graph. We establish 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 unexpected connections to the neighborhood complex, leading to multiple interesting questions.

This page was built for publication: Homotopy and the Homomorphism Threshold of Odd Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402179)