Consider the set $V=\{1,2,…,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random process: Each unordered pair $\{i,j\}$ of vertices, where $i≠j$, occurs as an edge in E with probability $p$, independently of the other unordered pairs.

A triangle in G is an unordered triple $\{i,j,k\}$ of distinct vertices, such that $\{i,j\}$, $\{j,k\}$, and $\{k,i\}$ are edges in $G$.

Define the random variable $X$ to be the total number of triangles in the graph $G$. Determine $var(X)$.

I need help because I can't think of a random variable without making it independent.

  • 1
    $\begingroup$ You may try to let $X$ be the sum of indicators of each possible triangle in the graph. By counting the vertices, there are a total $\displaystyle \binom {n} {3}$ of them. Although there are some dependency between them, it is manageable. To compute the covariance between two indicators, you need to know the number of common edges shared by them. You can compute for each case, and count the number of cases, and sum them up. $\endgroup$ – BGM Apr 14 '18 at 13:44

Thanks to BGM's hint, I came up with


This is because the only way that the triangles be dependent is if they share 1 edge, and that happens when we choose 4 points. This is multiplied by 4, since there are 4 ways to draw the 2 triangles that share an edge. Furthermore, $E(X)=p^3$, and the covariance of the edge-sharing triangles is $p^5-p^6$.

Am I missing anything?


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.