# Show that it is possible to color the edges of $K_n$ with at most $3 \sqrt n$ colors so that there are no monochromatic triangles.

Show that it is possible to color the edges of $$K_n$$ with at most $$3 \sqrt n$$ colors so that there are no monochromatic triangles.

(This was previous question and I get an explanation in the comments: Does this problem make a sense? I would expect at least, not at most. Where is my thinking wrong?)

Here is a solution: Actually, the problem is trivial. Proceed inductively.

Just split $$K_n$$ in to two parts with $${n\over 2}$$ elements in both if $$n$$ is even or $${n-1\over 2}$$ and $${n+1\over 2}$$ elements if $$n$$ is odd. Color all edges between this parts with one color. In one part we will not use more than $$3\sqrt{n+1\over 2}$$ colors. So we have used $$3\sqrt{n+1\over 2} +1$$ colors and all we have to check if $$3\sqrt{n+1\over 2} +1\leq 3\sqrt{n}$$ which is true.

Since I found this here, problem 41 I wonder how to solve it with a probabilistic method?

• With "at least" it would be trivial, you would give each edge a different color and voila. The point is how to do it using a small number of colors. – Michal Adamaszek Aug 13 at 11:09
• Let $n=16$. You want to ask: is it possible to color the edges of $K_{16}$ with at least $12$ colors and have no monochromatic triangles. Sure, we color each edge with a different color and we used $120$ colors, which is at least $12$, so problem solved. If you ask can we do it with at most $12$ colors it becomes more interesting. – Michal Adamaszek Aug 13 at 11:20
• But you can not color $K_{16}$ with two colors to not having monocolor triangle. Can you? @MichalAdamaszek – Aqua Aug 13 at 11:28
• You should find a coloring with some number of colors less than $3\sqrt{n}$, not with every possible number of colors less than $3\sqrt{n}$. For example coloring $K_{16}$ with $4$ colors solves the problem for $n=16$. – Michal Adamaszek Aug 13 at 11:31
• Here is a long formulation. Prove that for every integer $n$ there exists an integer $k$ such that $k\leq 3\sqrt{n}$ and such that the edges of $K_n$ can be colored with exactly $k$ colors and without monochomatic triangles. – Michal Adamaszek Aug 13 at 11:37

Fix $$3\sqrt{n}$$ colors. For each edge, choose one of those $$3\sqrt{n}$$ colors uniformly at random to color it with, with the random choice being independent for each edge.

The probability a given three vertices form a monochromatic triangle is $$(\frac{1}{3\sqrt{n}})^2 = \frac{1}{9n}$$.

The number of triangles whose three edge colorings are not independent of a given triangle is $$3n-8$$ (the triangle itself and the at most $$n-3$$ triangles sharing a given edge of the given triangle).

It holds that $$e\frac{1}{9n}(3n-7) \le 1$$, so by Lemma II, there is a nonzero probability that there are no monochromatic triangles, as wanted.

• Can you tell me please, why is 2. senence true. Is not it on $^3$? – Aqua Aug 18 at 6:58
• @Aqua If $k$ is the number of colours, the probability that a given triangle has all $3$ edges of a specified colour is $1/k^3$; the probability that all $3$ edges are the same colour (any colour) is $1/k^2$. (If I toss $3$ coins, the probability that they all come up heads is $1/8$, the probability that they all come up tails is $1/8$, but the probability that they all match is $1/4$.) – bof Aug 18 at 7:05
• So we have event $A_i$ ...i-th triangle is monochromatic, and we want to see what is a probability that none of it occurs? @bof – Aqua Aug 18 at 7:24
• This is very nice solution. And I would say this is pretty much straightforward proof, geedy. You just have to know LLL to check how much that greedines cost you. – Aqua Aug 18 at 7:36
• Do you know a solution without LLL? – Aqua Aug 18 at 11:43