On February 28, 2023, Maya Sankar from Stanford University gave a talk at the Discrete Math Seminar about an extremal problem on 2-dimensional simplicial complexes analogous to Mader’s theorem on the number of edges in a graph without a subdivision of a fixed complete graph. The title of her talk was “The Turán Numbers of Homeomorphs“.
Let be a 2-dimensional simplicial complex. Denote by the maximum number of 2-simplices in an -vertex simplicial complex that has no sub-simplicial complex homeomorphic to . The asymptotics of have recently been determined for all surfaces . I will discuss these results, as well as ongoing work bounding for arbitrary 2-dimensional simplicial complexes .
Fix and consider a family F of -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 -free. Specifically, we construct a family of dense -free graphs with no -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.
