1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ By "color the triangles", you just mean color the edges, don't you? $\endgroup$
    – LeechLattice
    Sep 17, 2018 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, 2018 at 5:09
  • $\begingroup$ @bof: Thank you for your suggestion. I just edited. $\endgroup$
    – Joe
    Sep 17, 2018 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, 2018 at 9:23

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.