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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.