Variance of subgraph counts

Question

I try to calculate the variance of the number of triangles in the uniform model $G_{n, m}$ where $m = \lfloor tN \rfloor$ for $t \in (0,1)$ fixed. I think the variation is $O(n^3)$, but I can not show that. Any help is welcome.

Answer 1

If $X$ is the number of triangles in $G_{n,m}$, then $X^2$ is the number of ordered pairs of triangles. We can compute $\mathbb E[X^2]$ by writing $X^2$ as a sum of indicator variables: one indicator variable for each ordered pair of triangles in the complete graph $K_n$, which equals $1$ if that ordered pair is present in $G_{n,m}$ and $0$ otherwise.

You probably already know how to compute $\mathbb E[X]$, but if not, the approach is similar. From here, we can compute the variance as $\mathbb E[X^2] - \mathbb E[X]^2$, and this is the easiest way to find the variance.

When finding the expected value of each indicator variable, keep in mind that there are several types of ordered pairs of triangles:

• There are $\binom n3$ ordered pairs which are just the same triangle written twice. Three edges have to be present for such an ordered pair to appear in $G_{n,m}$, so the probability for each one is $\binom{N-3}{m-3}/\binom{N}{m}$.
• There are $3\binom n3 (n-3)$ ordered pairs in which the two triangles share an edge. Five edges have to be present for such an ordered pair to appear in $G_{n,m}$, so the probability for each one is $\binom{N-5}{m-5}/\binom{N}{m}$.
• The remaining $\binom n3^2 - \binom n3 - 3\binom n3 (n-3)$ ordered pairs have no shared edges. Six edges have to be present for such an ordered pair to appear in $G_{n,m}$, so the probability for each one is $\binom{N-6}{m-6}/\binom{N}{m}$.

(I'm taking $N = \binom m2$ here, which I assume is also how you're using it in the question.)

From here, you can find an expression for the variance, and the remaining work (which I won't spare you) is determining its asymptotic behavior.

To be honest, this is much easier when working in the $G_{n,p}$ model, but I assume you have some reason not to do that.