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 $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics of $\text{ex}_{\hom}(n,X)$ have recently been determined for all surfaces $X$. I will discuss these results, as well as ongoing work bounding $\text{ex}_{\hom}(n,X)$ for arbitrary 2-dimensional simplicial complexes $X$.
Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-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 $C_{2r+1}$-free. Specifically, 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 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.
