0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$? $\endgroup$ – 2468 Dec 2 '18 at 15:28
  • 1
    $\begingroup$ @2468 Point 1: It's an integer inequality, so $n < m$ is the same as $n+1 \le m$. $\endgroup$ – Henno Brandsma Dec 2 '18 at 15:30
  • $\begingroup$ @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. $\endgroup$ – Henno Brandsma Dec 2 '18 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.