PROVED
This has been solved in the affirmative.
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?
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].
This problem is
#36 in Ramsey Theory in the graphs problem collection.
View the LaTeX source
This page was last edited 18 January 2026. View history
Additional thanks to: Zach Hunter
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #565, https://www.erdosproblems.com/565, accessed 2026-04-11
