Logo
All Random Solved Random Open
1 solved out of 2 shown (show only solved or open)
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
SOLVED - $100
Does there exist a graph $G$ with at most $10^{10}$ many vertices which contains no $K_4$, and yet any $2$-colouring of the edges produces a monochromatic $K_3$?
Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) Let this particular Folkman number be denoted by $N$.

Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the initial challenge of Erdős [Er75d] to beat $10^{10}$.

Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.

See also the entry in the graphs problem collection.