Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
Abstract
We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that δhom({C3,C5},{C3})=1/9. Equivalently, for every ε>0, every n-vertex graph of odd girth at least $7$ and minimum degree at least (1/9+ε)n admits a homomorphism to a triangle-free graph of size bounded by a function of ε, while there exist graphs of odd girth at least $7$ and minimum degree at least (1/9−ε)n for which no such bounded-size triangle-free homomorphic image exists. More generally, for every t≥ 3, we prove δhom({C3,C5},{Kt})=1/3t. In particular, for every proper monotone class 𝒞 of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in 𝒞 is positive. We further extend this phenomenon to arbitrary odd girth: for every k≥ 2 and every proper monotone subclass 𝒞 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 𝒞 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.
Related
- On the structure of graphs with given odd girth and large algebraic connectivity
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- On high-girth layered graphs of large Turán density in a hypercube
- Distinguishing graphs with simple spectrum by homomorphism counts
- Unbalanced distance-biregular graphs with girth deficiency two
BibTeX
@misc{bourneuf2026asymmetric,
title = {{Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth}},
author = {Romain Bourneuf and Raphael Steiner and Stéphan Thomassé and Yuval Wigderson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25390},
eprint = {2609.25390},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25390},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
AU - Romain Bourneuf
AU - Raphael Steiner
AU - Stéphan Thomassé
AU - Yuval Wigderson
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.25390
UR - https://arxiv.org/abs/2609.25390
AB - We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that δ_hom({C_3,C_5},{C_3})=1/9. Equivalently, for every ε>0, every n-vertex graph of odd girth at least $7$ and minimum degree at least (1/9+ε)n admits a homomorphism to a triangle-free graph of size bounded by a function of ε, while there exist graphs of odd girth at least $7$ and minimum degree at least (1/9−ε)n for which no such bounded-size triangle-free homomorphic image exists. More generally, for every t≥ 3, we prove δ_hom({C_3,C_5},{K_t})=1/3t. In particular, for every proper monotone class 𝒞 of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in 𝒞 is positive. We further extend this phenomenon to arbitrary odd girth: for every k≥ 2 and every proper monotone subclass 𝒞 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 𝒞 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.
ER -