Robust (rainbow) subdivisions and simplicial cycle
István Tomon · Advances in Combinatorics · 2023
One of the oldest results in graph theory is [Mantel's Theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem), which asserts that every $n$-vertex graph with more than $n^2/4$ edges contains a triangle. An extension of the result, [Turán's Theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem) gives an exact bound on the number of edges guaranteeing the existence of a complete graph, and, more generally, [Erdős–Stone Theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem) gives the asymptotically tight bound on the number of edges guaranteeing the existence of a fixed graph with chromatic number at least three. Significantly lower density thresholds apply when a _subdivision_ of a fixed graph is sought: a classical result of Mader from 1967 states that if an $n$-vertex graph $G$ avoids a subdivision of a fixed graph, then the number of edges of $G$ is linear in $n$. This paper provides an extension of the classical result of Mader to $\ell$-subdivisions of complete graphs with polynomial number vertices: if $\ell$ is an odd integer that is large enough in terms of $\alpha\in (0,1/2)$, then any $n$-vertex graph with at least $n^{1+\alpha}$ edges contains an $\ell$-subdivision of a complete graph of order $n^{c\alpha}$. The result generalizes to properly edge-colored host graphs where a subdivision is required to have all edges colored differently; another extension given in the paper concerns $3$-uniform hypergraphs where a triangulation of the cylinder or the Mőbius strip (as analogues of even and odd cycles in graphs) is sought.