All Random Solved Random Open
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)}.\]

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter