Problem 129

Erdős Problem #129: declared status 'open'. Formalized: no. Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours. Prove that there is a constant $C=C(r)>1$ such that$$R(n;3,r) < C^{\sqrt{n}}.$$ Current best: Erd\H{o}s thought it likely that for all $r,k\geq 2$ there exists some $C_1,C_2>1$ (depending only on $r$) such that$$C_1^{n^{1/k-1}}< R(n;k,r) < C_2^{n^{1/k-1}}.$$Antonio Girao has pointed out that this problem as written is easily disproved, and indeed $R(n;3,2) \geq C^{n}$: The obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), provided $N \leq C^n$ for some absolute constant $C>1$. Prize: no. Tags: graph theory, ramsey theory.