Logo
All Random Solved Random Open
1 solved out of 6 shown (show only solved or open)
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).\]
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$.

See also the entry in the graphs problem collection.

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).\]
A problem of Erdős and Graham. Erdős [Er81c] gives the bounds \[k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}.\] Chung and Graham [ChGr75] showed that \[R(C_4;k)>k^2-k+1\] when $k-1$ is a prime power and \[R(C_4;k)\leq k^2+k+1\] for all $k$.

See also the entry in the graphs problem collection.

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$.

See also the entry in the graphs problem collection.

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].

See also the entry in the graphs problem collection.

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 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.\] For example this implies that \[R(K_{3,3};k) \ll k^3.\] Using Turán numbers one can show that \[R(K_{3,3};k) \gg \frac{k^3}{(\log k)^3}.\]

See also the entry in the graphs problem collection.