Graphs with large odd cycles need minimum connections for small triangle-free mappings
Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
Discrete Mathematics
Summary
The authors studied special large graphs that avoid certain small odd cycles and explored how connected these graphs must be to simplify them into triangle-free graphs with a limited size. They found exact numbers that show when this simplification is possible and when it is not. Their results disprove previous guesses and reveal surprising differences compared to related graph coloring problems. The work uses advanced mathematical tools, including geometric constructions and combinatorial methods, to prove these properties.
What this means in practice
- •For network designers: Design connectivity requirements for network topologies avoiding short cycles to enable simplified conflict-free routing via small triangle-free graph models.
- •For combinatorial optimization engineers: Use homomorphism thresholds to know when large cycle-free graphs can be reduced to small, well-structured representations for optimization algorithms.
A theory result. No direct application yet.
Authors
Romain Bourneuf, Raphael Steiner, Stéphan Thomassé, Yuval Wigderson
Abstract
We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $δ_{\mathrm{hom}}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$. Equivalently, for every $\varepsilon>0$, every $n$-vertex graph of odd girth at least $7$ and minimum degree at least $(1/9+\varepsilon)n$ admits a homomorphism to a triangle-free graph of size bounded by a function of $\varepsilon$, while there exist graphs of odd girth at least $7$ and minimum degree at least $(1/9-\varepsilon)n$ for which no such bounded-size triangle-free homomorphic image exists. More generally, for every $t\geq 3$, we prove $δ_{\mathrm{hom}}(\{C_3,C_5\},\{K_t\})=\frac{1}{3t}$. In particular, for every proper monotone class $\mathcal C$ of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. We further extend this phenomenon to arbitrary odd girth: for every $k\geq 2$ and every proper monotone subclass $\mathcal C$ of the class of graphs of odd girth at least $2k-1$, the threshold for graphs of odd girth at least $2k+3$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. These results disprove conjectures of Gishboliner, Hurley and Wigderson and exhibit a sharp contrast with the corresponding zero chromatic-threshold results. Our lower-bound constructions are based on high-dimensional Borsuk graphs, while the matching upper bounds use regularity arguments to recover the structure underlying these constructions.