# monochromatic induced subgraph in a complete 3-partite graph

$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?

• By "color the triangles", you just mean color the edges, don't you? – LeechLattice Sep 17 '18 at 5:03
• Assign a color to a triangle means to color the three edges of the triangle with that special color. – Joe Sep 17 '18 at 5:09
• @bof: Thank you for your suggestion. I just edited. – Joe Sep 17 '18 at 17:08
• 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. – Ben Barber Sep 18 '18 at 9:23

• $O(\log n)$ (the optimal constant is almost certainly unknown) – Fedor Petrov Sep 17 '18 at 18:45