Paperlane

no. 9 · Thursday 5 November 2026

Off-Diagonal Induced Ramsey Numbers

Bruno Andrades, Marcelo Campos, Rafael Filipe and Anastasiia Kats

math.CO · 14 pp

Abstract

Given graphs $F$ and $H$, the induced Ramsey number $r_{\mathrm{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_{\mathrm{ind}}(F,H) \leq 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.

comments
14 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.06886 ↗