Skip to content
Preprint

Off-Diagonal Induced Ramsey Numbers

Nov 2026 · 0 citations · 15 references
Mathematics

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\"omel and R\"odl 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\"omel and R\"odl with the hypergraph container method.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.