Homotopy and the Homomorphism Threshold of Odd Cycles

preprint2022arXivOpen access

Abstract

Consider a family F\mathcal F of C2r+1C_{2r+1}-free graphs, where r≥2r\geq 2. Suppose that each graph in F\mathcal F 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 F\mathcal F are homomorphic to a complete graph of bounded size. Considering instead homomorphic images which are themselves C2r+1C_{2r+1}-free, we construct a family of dense C2r+1C_{2r+1}-free graphs with no C2r+1C_{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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.