Probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common

51 Views Asked by At

In the classic paper of Erdos,Renyi On the evolution of random graphs[page 7] ,it is argued that the probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common is given by $1-\frac{{n\choose 2N}(2N)!}{2^N N!{{n \choose 2}\choose N}} = \mathcal{O}(\frac{N^2}{n})$.

Here $n$ is order and $N$ is size of the random graph.

Can anyone please describe how the asymptotic formula is derived? IN general, how to derive such results involving factorials and powers?

1

There are 1 best solutions below

0
On BEST ANSWER

An important condition on $N$ in that paper is that $N = o(n^{1/2}).$ This allows us to more easily deal with the binomial coefficient terms. Namely, since $N = o(n^{1/2})$, we have that $$ {n \choose 2N} = (1+o(1)) \frac{n^{2N}}{(2N)!}, $$ and $$ {{n \choose 2} \choose N} = (1+o(1)) \frac{ {n \choose 2}^N}{N!}. $$ But we will need to know more about these $o(1)$ terms and so we have to go deeper. To do this, let's expand the first binomial expression: \begin{align*} {n \choose 2N} &= \frac{1}{(2N)!} \prod_{i=0}^{2N-1} (n - i) \\&= \frac{n^{2N}}{(2N)!} \prod_{i=0}^{2N-1} \left( 1 - \frac{i}{n} \right). \end{align*} Further, note that \begin{align*} \prod_{i=0}^{2N-1} \left( 1 - \frac{i}{n} \right) &= \exp \sum_{i=0}^{2N-1} \log \left(1- \frac{i}{n}\right) \\ & = \exp \sum_{i=0}^{2N-1} \left( - \frac{i}{n} + O\left(\frac{N^2}{n^2}\right) \right) \\&= \exp \left( \frac{-2N(2N-1)}{n} + O\left( \frac{N^3}{n^2}\right)\right) \\&= \exp \left(O \left( \frac{N^2}{n} \right)\right) = 1+ O\left( \frac{N^2}{n} \right). \end{align*} Thus $$ {n \choose 2N} = \left(1+O\left(\frac{N^2}{n}\right)\right)\frac{n^{2N}}{(2N)!}. $$ The asymptotic expression for the other binomial expression can be shown using a similar method to get $$ {{n \choose 2} \choose N} = \left(1+O\left(\frac{N^2}{{n\choose 2}}\right)\right)\frac{{n \choose 2}^{N}}{N!}. $$

Putting these all together, we have that \begin{align*} \frac{ { n \choose 2N} (2N)!} {2^N N! {{n \choose 2} \choose N}} &= \left(1+O\left(\frac{N^2}{n}\right)\right) \frac{ n^{2N}}{2^N {n \choose 2}^N} \\&= \left(1+O\left(\frac{N^2}{n}\right)\right) \frac{n^{2N}}{2^N n^N (n-1)^N/2^N} \\&= \left(1+O\left(\frac{N^2}{n}\right)\right) \frac{1}{\left(1-\frac{1}{n}\right)^N}. \end{align*} Now note that $\left(1-\frac{1}{n}\right)^N = 1+O\left(\frac{N}{n}\right).$

As a consequence, $$ \frac{ { n \choose 2N} (2N)!} {2^N N! {{n \choose 2} \choose N}} = 1+O\left(\frac{N^2}{n}\right). $$

In this case, we did not need to approximate the factorials since each factorial was divided out. If you want an asymptotic formula for a factorial, you would use Stirling's approximation. Namely, $$ n! = (1+o(1)) \sqrt{2\pi \, n} \, \left(\frac{n}{e}\right)^n. $$ If you wanted to approximate further, that $o(1)$ error term above is actually on the order of $1/n$.