Logo
All Random Solved Random Open
1 solved out of 2 shown (show only solved or open)
OPEN
Show that if $G$ has $\binom{n}{2}$ edges then \[R(G) \leq R(n).\] More generally, if $G$ has $\binom{n}{2}+t$ edges with $t\leq n$ then \[R(G)\leq R(H)\] where $H$ is the graph formed by connected a new vertex to $t$ of the vertices of $K_n$.
In other words, are cliques extremal for Ramsey numbers. Asked by Erdős and Graham.

See also the entry in the graphs problem collection.

SOLVED
Is it true that if $G$ has $m$ edges then \[R(G) \leq 2^{O(m^{1/2})}?\]
This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter