The homomorphism threshold of odd cycle C2k−1 is below 1/(2k−1)
Abstract
The homomorphism threshold δhom(H) of a graph H asks how large the minimum degree of an H-free graph has to be in order to force a homomorphism to a bounded H-free graph. Determining this threshold is in general very difficult, and the odd cycles C2k−1 are among the most important open cases for k≥ 3. Ebsen and Schacht proved the general upper bound δhom(C2k−1)≤1/(2k−1), while a breakthrough of Sankar, using topological methods and a graph-theoretic analogue of homotopy equivalence, gave the first positive lower bound. The value 1/(2k−1) appeared particularly compelling: Ebsen and Schacht obtained the same exact threshold when all odd cycles of length at most 2k−1 are forbidden, Huang, Liu, Rong and Xu later proved that it is the exact blowup threshold of C2k−1, and Letzter and Snyder also explicitly asked whether δhom(C5)=1/5. Surprisingly, we show that the upper bound can be improved. More precisely, for every integer k≥3, we prove 1/(2((k−1)4k−5(2k−1)+((k−1)4k−5−1)/(k−2))) ≤ δhom(C2k−1) ≤ (4(k−1))/(4(k−1)(2k−1)+1) < 1/(2k−1). The new lower bound comes from a new graph-theoretic construction based on a sparse homomorphism theorem of Nešetřil and Zhu, and it improves Sankar's quantitative bound. The improved upper bound follows from a new structural argument that controls common neighborhoods along short odd paths. Our results have various consequences, in particular, every odd cycle of length at least five has pairwise distinct chromatic, homomorphism, polynomial removal, and linear removal thresholds, resolving two conjectures of Fox and Wigderson.
Related
- Ideal MHD below the classical well-posedness threshold
- Threshold and Below-Threshold Dynamics for the Energy-Critical NLS: The Higher-Kinetic-Energy Regime
- Magnetic norm inflation below the velocity regularity threshold for viscous non-resistive MHD
- Below-threshold Bistability and Implementation Lag in a Simplex Model of Radical Vote-Share Dynamics
- Rough paths below the Young threshold: an exact scale calculus and the locality phase transition at one quarter
BibTeX
@misc{wang2026homomorphism,
title = {{The homomorphism threshold of odd cycle $C_2k-1$ is below $\frac12k-1$}},
author = {Jian Wang and Shipeng Wang and Zixiang Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20237},
eprint = {2609.20237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20237},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The homomorphism threshold of odd cycle C_2k−1 is below 1/(2k−1)
AU - Jian Wang
AU - Shipeng Wang
AU - Zixiang Xu
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20237
UR - https://arxiv.org/abs/2609.20237
AB - The homomorphism threshold δ_hom(H) of a graph H asks how large the minimum degree of an H-free graph has to be in order to force a homomorphism to a bounded H-free graph. Determining this threshold is in general very difficult, and the odd cycles C_2k−1 are among the most important open cases for k≥ 3. Ebsen and Schacht proved the general upper bound δ_hom(C_2k−1)≤1/(2k−1), while a breakthrough of Sankar, using topological methods and a graph-theoretic analogue of homotopy equivalence, gave the first positive lower bound. The value 1/(2k−1) appeared particularly compelling: Ebsen and Schacht obtained the same exact threshold when all odd cycles of length at most 2k−1 are forbidden, Huang, Liu, Rong and Xu later proved that it is the exact blowup threshold of C_2k−1, and Letzter and Snyder also explicitly asked whether δ_hom(C_5)=1/5. Surprisingly, we show that the upper bound can be improved. More precisely, for every integer k≥3, we prove 1/(2((k−1)^4k−5(2k−1)+((k−1)^4k−5−1)/(k−2))) ≤ δ_hom(C_2k−1) ≤ (4(k−1))/(4(k−1)(2k−1)+1) < 1/(2k−1). The new lower bound comes from a new graph-theoretic construction based on a sparse homomorphism theorem of Nešetřil and Zhu, and it improves Sankar's quantitative bound. The improved upper bound follows from a new structural argument that controls common neighborhoods along short odd paths. Our results have various consequences, in particular, every odd cycle of length at least five has pairwise distinct chromatic, homomorphism, polynomial removal, and linear removal thresholds, resolving two conjectures of Fox and Wigderson.
ER -