Event Series
Event Type
Seminar
Thursday, April 14, 2022 2:00 PM
Maya Sankar (Stanford)

Fix a forbidden subgraph H and a constant δ. Suppose G is an H-free graph with minimum degree at least δ|V(G)|. We are interested in the following question: for which δ do all such G have a shared finite H-free homomorphic image? For r > 1, we construct a family of dense C_{2r+1}-free graphs with no shared finite C_{2r+1}-free homomorphic image. This provides the first nontrivial lower bound on the homomorphism threshold of odd cycles of length at least five and answers a question of Ebsen and Schacht. Along the way, we introduce a version of homotopy theory for graphs, supplying a new technique to describe a graph's topological structure.