$H=(V_1\cup V_2 \cup V_3, E)$ is a complete $3$ partite graph such that $|V_1|=|V_2|=|V_3|=n$ . Color the edges with three colors.

My question is: Is it possible to find sets $V_1' \subset V_1, V_2' \subset V_2$ and $V_3' \subset V_3$, such that all edges between $V_1', V_2'$ and $V_3'$ have the same color and also $|V_i'|\geq \epsilon n$ for $i=1,2,3.$?

Could someone please give a reference for this problem?

  • $\begingroup$ By "color the triangles", you just mean color the edges, don't you? $\endgroup$ – LeechLattice Sep 17 '18 at 5:03
  • 2
    $\begingroup$ Assign a color to a triangle means to color the three edges of the triangle with that special color. $\endgroup$ – Joe Sep 17 '18 at 5:09
  • $\begingroup$ @bof: Thank you for your suggestion. I just edited. $\endgroup$ – Joe Sep 17 '18 at 17:08
  • $\begingroup$ This fails very hard, as you can colour all of the edges from $V_1$ to $V_2$ red and all other edges blue and not even have any monochromatic triangles. $\endgroup$ – Ben Barber Sep 18 '18 at 9:23

Of course no, even for the bipartite graph and two colors. Considering the random coloring we get that the expectation of the number of such sets is exponentially small.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your response. What is the largest size that we could get? $\endgroup$ – Joe Sep 17 '18 at 17:58
  • $\begingroup$ $O(\log n)$ (the optimal constant is almost certainly unknown) $\endgroup$ – Fedor Petrov Sep 17 '18 at 18:45
  • $\begingroup$ Could you please provide me a reference? I would like to see the solution. Thank you! $\endgroup$ – Joe Sep 17 '18 at 19:12

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.