Suppose that a random (simple, undirected) graph $G = (V, E)$ on a set of $n = 10$ vertices $V = \{v_1, . . . , v_n\}$ is constructed using the following random process: independently for each pair of vertices $v_i$, $v_j$ , $i \neq j$, with probability $1/2$ the edge $\{v_i, v_j\}$ is in the edge set $E$ (and with probability $1/2$ it is not in $E$).

A triangle inside a graph is any set of three distinct vertices such that there is an edge between every pair of them.

i. What is the expected number of triangles inside such a random graph on $10$ vertices? [5 marks]

ii. Prove that the probability that this random graph contains at least $45$ different triangles is at most $1/3$. (You may quote and use any theorem that we have proved in lectures.) [10 marks]

So I'm only on part i) but I'm a little bit stuck. So I have $P(E) = 1/2$ and $P(\bar E) = 1/2$. So then I think I'm correct in saying $P(T)$, which is the probability that there is a triangle, is $1/2*1/2*1/2 = 1/8$? From there though I'm too sure where to go. Any hints?

  • $\begingroup$ Whats with the instant downvote? Hardly helpful at all $\endgroup$ – BlackBruceLee Dec 4 '17 at 12:56

The probability of any particular triangle being present is $1/8$ as you say. Then by the linearity of expectation, you can get the expected number of triangles by multiplying $1/8$ by the total number of potential triangles.

This follows because we can think of the total number of triangles as the sum over possible triangles of the random variable which is $1$ if that triangle is present and $0$ otherwise. These variables are not independent, but that doesn't matter.

For the second part I suspect the result you're intended to quote is Markov's inequality.

  • $\begingroup$ Thanks for the help. So would the potential number of triangles be $10C3$....? This gives me 120 triangles. So expected number of triangles is 15. $\endgroup$ – BlackBruceLee Dec 4 '17 at 13:18
  • $\begingroup$ I think this is wrong, hence the -1. When you have triangles that share an edge, the probability of their occurence is not independent. $\endgroup$ – bat_of_doom Dec 4 '17 at 13:20
  • $\begingroup$ Oh okay, I see. Well now I'm not too sure what to do $\endgroup$ – BlackBruceLee Dec 4 '17 at 13:21
  • 1
    $\begingroup$ @bat_of_doom No, it's not wrong. The events are not independent, but they don't need to be. Google "linearity of expectation" for an explanation. $\endgroup$ – Especially Lime Dec 4 '17 at 13:29
  • $\begingroup$ @BlackBruceLee yes, you're correct with $15$. $\endgroup$ – Especially Lime Dec 4 '17 at 13:30

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.