Off-Diagonal Induced Ramsey Numbers

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)\le 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.

arXiv comment14 pages