Problem Statement
Let $R^*(G)$ be the induced Ramsey number: the minimal $m$ such that there is a graph $H$ on $m$ vertices such that any $2$-colouring of the edges of $H$ contains an induced monochromatic copy of $G$.
Is it true that\[R^*(G) \leq 2^{O(n)}\]for any graph $G$ on $n$ vertices?
Is it true that\[R^*(G) \leq 2^{O(n)}\]for any graph $G$ on $n$ vertices?
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Erdős and Rödl. Even the existence of $R^*(G)$ is not obvious, but was proved independently by Deuber [De75], Erdős, Hajnal, and Pósa [EHP75], and Rödl [Ro73].Rödl [Ro73] proved this when $G$ is bipartite. Kohayakawa, Prömel, and Rödl [KPR98] have proved that\[R^*(G) < 2^{O(n(\log n)^2)}.\]An alternative (and more explicit) proof was given by Fox and Sudakov [FoSu08]. Conlon, Fox, and Sudakov [CFS12] have improved this to\[R^*(G) < 2^{O(n\log n)}.\]This is true, and an upper bound of\[R^*(G) < 2^{O(n)}\]was proved by Aragão, Campos, Dahia, Filipe, and Marciano [ACDFM25].
See also the entry in the graphs problem collection.
Source: erdosproblems.com/565 | Last verified: January 15, 2026