Erdős Problems

Tags Prizes

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

#544: [Er81c]

graph theory, ramsey theory

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

#554: [Er81c]

graph theory, ramsey theory

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

#555: [Er81c]

graph theory, ramsey theory

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

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

#556: [Er81][Er81c]

graph theory, ramsey theory

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?

#557: [Er81c]

graph theory, ramsey theory

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.

#558: [Er81c]

graph theory, ramsey theory

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

Additional thanks to: Noga Alon