Variance in the number of triangles in a random graph of size n

Question

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.

Answer 1

Thanks to BGM's hint, I came up with

$Var(X)=nC3$$(p^3-p^6)+4*nC4(p^5-p^6)$

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?

Answer 2

Primarily typing this up for my own practice, but perhaps it may be useful to someone down the line.

Enumerate the $N=\binom n3$ triangles in the graph, and with each triangle associate the indicator random variable $I_i$, which takes value $1$ if the triangle is included in the graph and $0$ otherwise. Clearly we have $$X=\sum_{i=1}^N I_i.$$ We then have that $$\mathrm{Var}(X)=\mathrm{Var}\left(\sum_{i=1}^N I_i\right)=\sum_{i=1}^N \mathrm{Var}(I_i)+\sum_{i\neq j}\mathrm{Cov}(I_iI_j).$$ We can fairly easily compute that each $I_i$ is a Bernoulli random variable with $E(I_i)=p^3$ and $\mathrm{Var}(I_i)=p^3-p^6$. If triangles $T_i$ and $T_j$ share no edges, $I_i$ and $I_j$ are independent and thus $\mathrm{Cov}(I_iI_j)=0$. If $T_i$ and $T_j$ share an edge, then we actually have to do some work to compute $E(I_iI_j)=p^5$ (since there are $5$ edges in question and we need them all there for this product to be nonzero) and thus $$\mathrm{Cov}(I_iI_j)=E(I_iI_j)-E(I_i)E(I_j)=p^5-p^6$$ So now we have all of the ingredients together, and we just need to count how many of each term appears in the sum above. We know there are $\binom n3$ triangles in total in the graph, so the first term contributes a sum of $\binom n3(p^3-p^6)$. Now we have to count the number of (ordered) pairs of triangles that share an edge. Note that any such pair has four vertices involved in total, and each set of four vertices corresponds to twelve such pairs (any one of the edges can be the shared one, and then two orders). This yields a contribution of $12\binom n4(p^5-p^6)$. Putting everything together, we have $$\mathrm{Var}(X)=\binom n3(p^3-p^6)+12\binom n4(p^5-p^6),$$ which is different from Sally's answer but perhaps others can weigh in if I messed something up here.