OPEN

Show that
\[R(3,k+1)-R(3,k)\to\infty\]
as $k\to \infty$. Similarly, prove or disprove that
\[R(3,k+1)-R(3,k)=o(k).\]

This problem is #8 in Ramsey Theory in the graphs problem collection. See also [165].

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that
\[\lim_{k\to \infty}\frac{R(C_{2n+1};k)}{R(K_3;k)}=0\]
for any $n\geq 2$.

A problem of Erdős and Graham. The problem is open even for $n=2$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of
\[R(C_{2n};k).\]

SOLVED

Let $R(G;3)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that
\[R(C_n;3) \leq 4n-3.\]

A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that
\[R(T;k)=kn+O(1)\]
for any tree $T$ on $n$ vertices?

A problem of Erdős and Graham. Implied by [548].

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine
\[R(K_{s,t};k)\]
where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.

Chung and Graham [ChGr75] prove the general bounds
\[(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s\]
and determined
\[R(K_{2,2},k)=(1+o(1))k^2.\]
Alon, Rónyai, and Szabó [ARS99] have proved that
\[R(K_{3,3},k)=(1+o(1))k^3\]
and that if $s\geq (t-1)!+1$ then
\[R(K_{s,t},k)\asymp k^t.\]