# Lower bound bound for the Ramsey number $R_k(3,3,…,3)$

The question is:

Show that $$R_k(3,3,...,3)\geq 2^k+1$$. The upper bound part of this problem has been proved in the link How to obtain lower and upper bounds for Ramsey number $$R_k (3,3,\dots,3)$$, however the lower bound is not clearly shown procedurally because I want to make my understanding on this problem complete.

The statement you're trying to prove is equivalent to showing there is a colouring of the edges of a complete graph on $$2^k$$ vertices with $$k$$ colours such that no colour contains a triangle. You can do this by induction: take two copies of the colouring for $$k-1$$ and use a new colour for all the edges between them.

Consider the complete graph of order $$2^k$$ whose vertices are the bitstrings of length $$k$$. Give color $$i$$ to the edge between two bitstrings if they first differ in the $$i^{\text{th}}$$ bit.

Following the hint in the link: let $$n = 2^k$$ and consider the complete graph on the set $$\{0,1\}^k$$ and colour the edge between $$(x_1,\ldots,x_k) \neq (y_1,\ldots y_k)$$ by the colour $$c = \min(i: x_i \neq y_i)\in \{1,\ldots,k\}$$.

It's clear we cannot have a triangle of a fixed colour $$c$$: suppose

$$(x_1,\ldots,x_k),(y_1,\ldots,y_k),(z_1,\ldots,z_k)$$ is a triangle (three distinct points) where all three edges have the same colour $$c$$. This implies that $$x_i = y_i = z_i$$ for all $$i < c$$ and $$\{x_c,y_c, z_c\}$$ would have be three distinct values in $$\{0,1\}$$, which is absurd.

So this graph on $$2^k$$ points has a $$k$$-colouring without triangle, hence $$R_k(3,\ldots,3) > 2^k$$, and this is what you were required to show. No induction needed.

• Thanks. Does $2^k<R_k(3,...,3)\implies 1+2^k\leq R_k(3,...,3)?$ How can I justify whether $1+2^k\leq R_k(3,...,3) or 1+2^k\geq R_k(3,...,3)$? – 2468 Dec 2 '18 at 15:28
• @2468 Point 1: It's an integer inequality, so $n < m$ is the same as $n+1 \le m$. – Henno Brandsma Dec 2 '18 at 15:30
• @2468 Point 2: the Ramsey number is defined as the smallest $N$ such that all $k$-coloured complete $N$-graphs have a monochromatic triangle. $N=2^k$ is, by this construction, ruled out as such an $N$ so the minimum (where we are garanteed such a triangle) must be larger than this $N$. Constructions prove lower bounds. – Henno Brandsma Dec 2 '18 at 15:33