An exponential upper bound for induced Ramsey numbers

Abstract

The induced Ramsey number $R_{\mathrm{ind}}(H;r)$ of a graph $H$ is the minimum number $N$ such that there exists a graph with $N$ vertices for which all $r$-colourings of its edges contain a monochromatic induced copy of $H$. Our main result is the existence of a constant $C>0$ such that, for every graph $H$ on $k$ vertices, these numbers satisfy \begin{equation*} R_{\mathrm{ind}}(H; r) \le r^{C r k}. \end{equation*} When $r=2$, this resolves a conjecture of Erdős from 1975. For $r>2$, it answers a question of Conlon, Fox and Sudakov in a strong form.

Simplified and improved the presentation for journal submission; fixed typos and corrected some calculations