bounds for number related to colourings

Question

Let $R(r,s)$ be the minimum $n$ so that for all colourings of the edges of the complete graph $K_n$ on $n$ vertices with $2$ colours green and orange, there is a complete subgraph of $K_n$ with $r$ vertices whose edges are all green or a complete subgraph with $s$ vertices that are all orange. Show that $R(s,s) > (\sqrt{2} + 0.00000001)^{s-1}$ for $s\geq 2$ and $R(s,s) <3.999999999^s$ for all $s\geq 2.$

I know how to show that $R(s,s) > \sqrt{2}^{s-1}$ by showing that for any $s$-element subset of $V(K_n)$, the number of colourings where all the edges of $S$ are the same colour is less than the total number of colourings. But how can I improve this upper bound to the precision specified in the question? What might be useful? Induction? Recurrence relations?

Answer 1

Both of these problems are open. We don't have a lower bound $R(s,s) \ge C^s$ for any constant $C > \sqrt2$, and we don't have an upper bound $R(s,s) \le C^s$ for any constant $C < 4$.

We do have better bounds than $\sqrt 2^{s-1}$ and $4^s$.

• The argument for $R(s,s) > \sqrt 2^{s-1}$ you're describing can be strengthened: it shows that $R(s,s) > n$ whenever $\binom ns < 2^{\binom s2 - 1}$, and the best $n$ we can find in this way is asymptotically $(1+o(1))\frac{s}{\sqrt2 e} \sqrt 2^s$.
• You can prove by induction that $R(r,s) \le \binom{r+s-2}{s-1}$ and in particular $R(s,s) \le \binom{2s-2}{s-1}$, which is asymptotically $(1+o(1))\frac{1}{\sqrt{\pi s}} 4^s$.
• Wikipedia cites results due to Spencer and Conlon that improve on this, giving $$(1+o(1))\frac{\sqrt 2 s}{e}\sqrt2^s \le R(s,s) \le s^{-(c \log s)/(\log \log s)} 4^s.$$

However, a lower bound of $(\sqrt{2} + 0.00000001)^{s-1}$, or an upper bound of $3.999999999^s$, would be stronger than these results for sufficiently large $s$.