3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for your reply. I consider that my problem is precisely that I am used to working with the binomial model $G_{n,p}$. In this case, the variance is $O(n^4)$, because the second type of ordered pairs of triangles "dominates" the others. Why in the uniform model $G_{n,m}$ the first type of ordered pairs dominates the others? This is my doubt ... $\endgroup$ – JDAM Nov 3 '18 at 23:24
  • $\begingroup$ I get a similar result. (By the way, I have fixed a mistake in the probabilities I gave in my answer, but I don't know if you were going off of that or not to begin with.) In principle, this can happen when the main source of variance in the number of triangles is the variance in the number of edges of $G_{n,p}$, which goes away when we consider $G_{n,m}$. $\endgroup$ – Misha Lavrov Nov 3 '18 at 23:38
  • $\begingroup$ We do expect the variance in the number of edges to give a $\Theta(n^4)$ term no matter what. Roughly speaking, the number of edges deviates from $\binom n2 p$ by $O(n)$, which corresponds to a change in $p$ by $O(\frac1n)$. The difference between $\binom n3 p^3$ and $\binom n3 (p+\frac1n)^3$ is $\Theta(n^2)$, and then we square that to get a very sloppy estimate from the variance that arises in this way. $\endgroup$ – Misha Lavrov Nov 3 '18 at 23:43
  • $\begingroup$ Thanks for the great explanation. I have learned more about the difference between these two models. $\endgroup$ – JDAM Nov 5 '18 at 21:50

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.