PreprintCC BY 4.0arXiv
A Solution to the Kohayakawa-Prömel-Rödl Conjecture
Abstract
The induced Ramsey number rind(G,H) is defined as the minimum order of a graph F such that any 2-coloring of its edges with red and blue leads to either a red induced copy of G or a blue induced copy of H. In 1998, Kohayakawa, Prömel, and Rödl conjectured that for any fixed graph G, there exists a constant f=f(G) such that the induced Ramsey number rind(G, H) is bounded by |V(H)|f for every graph H. In this paper, we completely solve the Kohayakawa--Prömel--Rödl conjecture, which states that for any graphs G and H with |V(G)|=k≥2 and |V(H)|=t≥2, rind(G,H)≤ t60k2+3. This verifies the conjecture with f(G)=60|V(G)|2+3.
Related
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- AI's solution of Conjecture 9.1
- A positive solution to the Lp projection centroid conjecture
- A complete solution to the Boots-Royle/Cao-Vince conjecture
- A solution to a conjecture on the norm of the Copson operator minus the Identity for monotone sequences
BibTeX
@misc{zhong2026solution,
title = {{A Solution to the Kohayakawa-Prömel-Rödl Conjecture}},
author = {Chuang Zhong and Masaki Kashima and Yaping Mao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27478},
eprint = {2610.27478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27478},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Solution to the Kohayakawa-Prömel-Rödl Conjecture
AU - Chuang Zhong
AU - Masaki Kashima
AU - Yaping Mao
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27478
UR - https://arxiv.org/abs/2610.27478
AB - The induced Ramsey number r_ind(G,H) is defined as the minimum order of a graph F such that any 2-coloring of its edges with red and blue leads to either a red induced copy of G or a blue induced copy of H. In 1998, Kohayakawa, Prömel, and Rödl conjectured that for any fixed graph G, there exists a constant f=f(G) such that the induced Ramsey number r_ind(G, H) is bounded by |V(H)|^f for every graph H. In this paper, we completely solve the Kohayakawa--Prömel--Rödl conjecture, which states that for any graphs G and H with |V(G)|=k≥2 and |V(H)|=t≥2, r_ind(G,H)≤ t^60k^2+3. This verifies the conjecture with f(G)=60|V(G)|^2+3.
ER -