Ramsey Numbers and edge coloring

Question

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same colour.

Thanks.

Answer 1

Let $n=3 k!$ so our graph is $K_{3k!}$. Take an arbitrary vertex $u$. By the pigeonhole principle at least $\lceil \tfrac{n-1}{k} \rceil = 3(k-1)!$ of $u$'s edges share the same color. Let $V$ be a subset of size $3(k-1)!$ of the vertices that are attached to $u$ by the same color. We notice that $V$ induces the subgraph $K_{3(k-1)!}$ and that it must be colored by the remaining $k-1$ colors (otherwise you get a monochromatic triangle $[u,v_1,v_2]$).

This is recursive so we simply induct. The base case $k=1, n=3$ is trivial.

---

This argument actually gives us a nice bound on Ramsey numbers. Given $k$ colors, the smallest $n$ such that every $K_n$ has a monochromatic triangle is the Ramsey number $R(3,3,...,3)$ with $k$ threes. For aesthetic reasons, lets denote this as $\mathcal{R}_k$. We automatically get $\mathcal{R}_{k} \leq 3k!$, but by being greedy we can do better. We know $\mathcal{R}_1 = 3$. Now for two colors $k=2$, given an arbitrary vertex we want atleast 3 of its $n-1$ edges to be the same color. This means that $\lceil \tfrac{n-1}{2} \rceil = 3$. The smallest number that satisfies this equality is $n=6$. So $\mathcal{R}_2 \leq 6$. For $k=3$ we find the smallest number $n$ that satisfies $\lceil \tfrac{n-1}{3} \rceil = 6$ and we find $\mathcal{R}_3 \leq 17$. Similarly, $\mathcal{R}_4 \leq 66$. In general, we have the following relation $$ \begin{align} &\mathcal{R}_1 &=& 3 \\ &\mathcal{R}_k &\leq& k \, \mathcal{R}_{k-1} - k + 2 \\ \implies & \mathcal{R}_k & \leq& 1 + k! \sum_{j=0}^k \frac{1}{j!} < 1 + e\,k! \\ \end{align} $$