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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Michal Adamaszek Aug 13 at 11:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Michal Adamaszek Aug 13 at 11:20
  • 1
    $\begingroup$ But you can not color $K_{16}$ with two colors to not having monocolor triangle. Can you? @MichalAdamaszek $\endgroup$ – Aqua Aug 13 at 11:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michal Adamaszek Aug 13 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Can you tell me please, why is 2. senence true. Is not it on $^3$? $\endgroup$ – Aqua Aug 18 at 6:58
  • 1
    $\begingroup$ @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$.) $\endgroup$ – bof Aug 18 at 7:05
  • $\begingroup$ 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 $\endgroup$ – Aqua Aug 18 at 7:24
  • $\begingroup$ 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. $\endgroup$ – Aqua Aug 18 at 7:36
  • $\begingroup$ Do you know a solution without LLL? $\endgroup$ – Aqua Aug 18 at 11:43

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.