Ramsey multiplicity and extremal colorings for odd cycles
Abstract
The Ramsey number r(H) of a graph H is the minimum positive integer N such that every red/blue edge-coloring of the complete graph KN on N vertices contains a monochromatic copy of H. The Ramsey multiplicity M(H,n) is the minimum number of monochromatic copies of H over all red/blue edge-colorings of Kn. It is called threshold Ramsey multiplicity if n=r(H), and denoted by m(H). The only previously known general infinite family for which m(H) has been determined is stars, due to Harary and Prins (1974). Let Ck denote a cycle on k vertices. Conlon, Fox, Sudakov, and Wei (2022) conjectured that m(Ck)=(k−1)!/2 for every sufficiently large odd integer k. In this paper, we determine M(Ck,r(Ck)+ℓ) for every fixed nonnegative integer ℓ and all sufficiently large odd k, and characterize all extremal colorings, thereby confirming the conjecture. This is also a second general infinite family for which m(H) has been determined.
Related
- Bounds on the Threshold Ramsey Multiplicity of Ramsey Numbers with Many Colors
- Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
- The three-colour bipartite Ramsey number of sufficiently long even cycles
- Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
- The Ramsey threshold for trees versus odd cycles
BibTeX
@misc{huang2026ramsey,
title = {{Ramsey multiplicity and extremal colorings for odd cycles}},
author = {Ting Huang and Junying Lu and Jiabao Yang and Yaojun Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07285},
eprint = {2609.07285},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07285},
}
RIS
TY - UNPB
TI - Ramsey multiplicity and extremal colorings for odd cycles
AU - Ting Huang
AU - Junying Lu
AU - Jiabao Yang
AU - Yaojun Chen
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.07285
UR - https://arxiv.org/abs/2609.07285
AB - The Ramsey number r(H) of a graph H is the minimum positive integer N such that every red/blue edge-coloring of the complete graph K_N on N vertices contains a monochromatic copy of H. The Ramsey multiplicity M(H,n) is the minimum number of monochromatic copies of H over all red/blue edge-colorings of K_n. It is called threshold Ramsey multiplicity if n=r(H), and denoted by m(H). The only previously known general infinite family for which m(H) has been determined is stars, due to Harary and Prins (1974). Let C_k denote a cycle on k vertices. Conlon, Fox, Sudakov, and Wei (2022) conjectured that m(C_k)=(k−1)!/2 for every sufficiently large odd integer k. In this paper, we determine M(C_k,r(C_k)+ℓ) for every fixed nonnegative integer ℓ and all sufficiently large odd k, and characterize all extremal colorings, thereby confirming the conjecture. This is also a second general infinite family for which m(H) has been determined.
ER -