1
$\begingroup$

I can't seem to understand this question and I really don't know where to start. Could someone please give an explanation as to how to go about answering this?

  • A simple graph is formed randomly on the vertices $v_1,v_2,\dots,v_{20}$ in the following way: For each unordered pair of these vertices $\{v_i,v_j\}$, the edge $v_iv_j$ is in the graph with probability $1/3$ and is not in the graph with probability $2/3$.

What is the expected number of triangles contained in this graph?

$\endgroup$
  • $\begingroup$ There are $\binom{20}3$ potential triangles in $20$ vertices, and each triangle has probability $(\frac13)^3$ of being realized. $\endgroup$ – bof Jun 20 '16 at 11:07
  • $\begingroup$ @bof but the propability functions for the triangles are not all mutually independent (if $(1,2,3)$ is a triangle and the edges $(2,4)$ and $(3,4)$ are part of the graph, then $(2,3,4)$ has probability one) $\endgroup$ – Max Jun 20 '16 at 11:14
  • 3
    $\begingroup$ @Max dependency is not bothering here. For each potential triangle create a random variable $X$ taking value $1$ if it occurs and $0$ otherwise. The sum of these rv's is the number of triangles. With linearity of expectation (also works under dependency) and symmetry we find $\binom{20}3\times\left(\frac13\right)^3$ for the expectation. $\endgroup$ – drhab Jun 20 '16 at 11:19
  • $\begingroup$ @Raux maybe try induction for the number of nodes to derive a formula? (just an unelaborated idea) $\endgroup$ – Max Jun 20 '16 at 11:19
  • $\begingroup$ true. (need moar characters) $\endgroup$ – Max Jun 20 '16 at 11:23
2
$\begingroup$

There are $\binom{20}3=1140$ potential triangles, corresponding to the $\binom{20}3$ three-element subsets of the vertex set $\{v_1,\dots,v_{20}\}.$ Define indicator variables $X_1,\dots,X_{1140},$ where $X_i=1$ if the $i^{\text{th}}$ potential triangle occurs in the random graph, and $X_i=0$ otherwise; thus $E(X_i)=(\frac13)^3=\frac1{27}.$ Then the number of triangles is $X=X_1+\cdots+X_{1140},$ and $$E(X)=E(X_1+\cdots+X_{1140})=E(X_1)+\cdots+E(X_{1140})=1140\cdot\frac1{27}=\frac{380}9.$$

$\endgroup$

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.