1
$\begingroup$

Actually I got this question in job interview and successfully failed it ( it was obvious eliminating question ). I recall the Ramsey theory and cited the famous result on existence of cliques with edges of same color. But they then asked me to discuss how to estimate the probability that in fully connected graph there is a clique where edge colors are all different? Namely, they said: "Imagine that in a fully-connected graph, each edge is painted with one of two colours. Estimate the probability that the graph contains a fully-connected subgraph on 3 vertices that has edges of different colours"

I read a lot of articles but it does not look as naive result, which anyone knows since college graduation. So any help/hints/links are highly appreciated.

Thank you!

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

If you're looking for a triangle where all colors are different, then you obviously don't have enough different colors for that when there are only $2$ colors, so the probability is $0$.

If you're looking for a triangle where both colors are represented, then such a triangle will automatically exists unless all edges in the original graph have the same color.

Namely, suppose that $(v_1,v_2)$ is black and $(v_3,v_4)$ is white. If $(v_2,v_3)$ is black, then $\{v_2,v_3,v_4\}$ is a triangle that has both a black and a white edge; otherwise $\{v_1,v_2,v_3\}$ is such a triangle. (And if the two edges already share a vertex, just $\{v_1,v_2,v_3,v_4\}$ will do).

Thus the probability we're looking for is $$ 1 - 2^{-\binom{n}{2}+1} $$ which, when $n$ is not very small, will be so close to $1$ as not to matter.

Things get more involved with different numbers than $2$ colors and $3$-cliques, but it doesn't sound like that was what you were asked.

$\endgroup$
3
  • $\begingroup$ Great, thank you! :-) If your reasoning was based on anything but common sense then please share relevant literature for refreshment. Case when there are more than 2 colors and 3-cliques is especially interesting $\endgroup$
    – Vast Academician
    Jan 27, 2018 at 15:54
  • $\begingroup$ Could you please elaborate more on formula? It's not very intuitive for me... $\endgroup$
    – Vast Academician
    Jan 27, 2018 at 16:10
  • $\begingroup$ @VastAcademician: There are $\binom n2$ edges in the graph. The probability that they are all black is $2^{-\binom n2}$. The probability that they are all whit is $2^{-\binom n2}$. The probability that they are all the same color is the sum of these (since "all black" and "all white") are mutually exclusive. that is $2\cdot 2^{-\binom n2} = 2^{-\binom n2+1}$. And the probability that both colors are represented is the opposite of that. $\endgroup$
    – hmakholm left over Monica
    Jan 27, 2018 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .