PreprintCC BY 4.0arXiv
Off-Diagonal Induced Ramsey Numbers
Abstract
Given graphs F and H, the induced Ramsey number rind(F,H) is the smallest integer n for which there exists a graph G on n vertices such that every red-blue colouring of E(G) contains either a blue induced copy of F or a red induced copy of H. A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph F, this number is polynomial in v(H). We prove this conjecture, showing that there is an absolute constant C > 0 such that rind(F,H) ≤ v(H)Cv(F)2 for all graphs F and H. The proof combines a variant of a random geometric construction of Kohayakawa, Prömel and Rödl with the hypergraph container method.
Related
BibTeX
@misc{andrades2026offdiagonal,
title = {{Off-Diagonal Induced Ramsey Numbers}},
author = {Bruno Andrades and Marcelo Campos and Rafael Filipe and Anastasiia Kats},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06886},
eprint = {2611.06886},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06886},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Off-Diagonal Induced Ramsey Numbers
AU - Bruno Andrades
AU - Marcelo Campos
AU - Rafael Filipe
AU - Anastasiia Kats
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06886
UR - https://arxiv.org/abs/2611.06886
AB - Given graphs F and H, the induced Ramsey number r_ind(F,H) is the smallest integer n for which there exists a graph G on n vertices such that every red-blue colouring of E(G) contains either a blue induced copy of F or a red induced copy of H. A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph F, this number is polynomial in v(H). We prove this conjecture, showing that there is an absolute constant C > 0 such that r_ind(F,H) ≤ v(H)^Cv(F)^2 for all graphs F and H. The proof combines a variant of a random geometric construction of Kohayakawa, Prömel and Rödl with the hypergraph container method.
ER -