2022/06/15 by Maya Sankar, Sankar, Maya · 1 citation
Computer Science · Mathematics · #05C35 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2206.07525
openalex publication_date 2022/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a family \mathcal F of C2r+1-free graphs, where r≥ 2. Suppose that each graph in \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 \mathcal F are homomorphic to a complete graph of bounded size. Considering instead homomorphic images which are themselves C2r+1-free, we construct a family of dense C2r+1-free graphs with no C2r+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.