6
$\begingroup$

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the expectation $EN_G$. This means that whenever expectation tends to zero then $N_G$ also tends to zero and we have $$\frac{N_G - EN_G}{EN_G} \overset{p}{\rightarrow} 0$$ Now we are interested to know that does central limit theorem also true: i.e. \begin{equation} \cfrac{N_G-EN_G}{\sqrt{Var N_G}}\overset{d}{\rightarrow}\mathcal{N}(0,1) \end{equation} For $\mathcal{N}(0,1)$ be the standard normal distribution.

As Poisson limit theorem for the number of copies of $G$, this fact can also be proved by moments method. So if we can prove that if we have a sequence of random variables and for any $k$, the $k$th moment tends to the $k$th moment of standard normal random variable, then this convergence in distribution also holds.

In the way for to prove this; we need to prove that $k$th moment of $E(\frac{N_G - EN_G}{\sqrt{Var N_G}})^k$ is equal to $\frac{E(N_G - EN_G)^k}{(\sqrt{Var N_G})^k}$, for when that $k$ is even. For to do this we use the indicator function and the $k$ collection of vertices which can be pairwise disjoint or maybe not; i.e maybe the first collection and the second are not disjoint or the the second and third and ... and maybe all of them are not disjoint!

But we can use some notation in this case that maybe will help me. We can consider a graph of relations between our collections and we can say that two collections are related to each other when they are not disjoint. So we can consider a graph on $k$ vertices such that each vertices is one of our collections and two vertices are adjacent when their collection do intersect (have intersection).

And it turns out that there is three situation here for such graph $H$ on $k$ vertices with the above mentioned specification.

In fact we have a lot of graphs here, i.e. $2^{{k \choose 2}}$ graphs; but we have only three different situations:

1)$H$ has isolated vertex.

2) $H$ is perfect matching.

3) else.

Now let me to put what I said in equations for to understand the proof of second case better:

Lets drop the denominator \begin{eqnarray} E(N_G-EN_G)^k &=& E(\sum_i(I_i-EI_i))^k\\ &=&\sum_{i_i,\ldots,i_k\in I}E((I_{i_1}-EI_{i_1})\cdots(I_{i_k}-EI_{i_k})) \end{eqnarray} where $N_G=\sum_iI_i$.

Now $i_j\sim i_k \iff i_j\cap i_k \ne \emptyset$ so we get \begin{equation} =\sum_{H:V(H)=k}\sum_{\overset{(i_1,\ldots,i_k)}{j\sim h \text{ in } H \iff i_j\sim i_h}}E(I_{i_1}-EI_{i_1})\cdots (I_{i_k}-EI_{i_k}) \end{equation}

We can prove the first one as follows:

Set $i_1$ isolated vertex. Then $I_{i_1}$ is independent of $(I_{i_2}, \cdots , I_{i_k})$. Then $E((I_{i_1} - EI_{i_1}) \cdots (I_{i_k} - EI_{i_k})) = E(I_{i_1} - EI_{i_1}) E(I_{i_2} - EI_{i_2}) \cdots E(I_{i_k} - EI_{i_k}) = 0$. And we are done. And this means that for the first case we have $o((Var N_G)^{\frac{k}{2}})$

Now we need to prove that the sum in the second case converges to $(k-1)!!Var(N_G)^{k/2}$

But for to prove the second one I need help.

Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.