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?
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)}.\]