Lower bound for $R(3, 3,\ldots, 3)$

541 Views Asked by At

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges of a complete graph $K_{2^k}$ using k colours in such a way that there does not exist a triangle with edges of the same colour. It is fairly easy to do when k is 2 or 3 (examples are below) but I cannot figure out an idea/pattern how to do it in general.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

Let the vertices of the complete graph of order $2^k$ be bitstrings of length $k$. For any two vertices $x\ne y,$ choose some $i\in\{1,\dots,k\}$ such that $x$ and $y$ differ in the $i^\text{th}$ bit, and colour the edge $xy$ with the $i^\text{th}$ colour. Clearly, there is no monochromatic triangle.