4
$\begingroup$

If $N_c=\lfloor \frac{1}{2}n\log n+cn\rfloor$ for some integer $n$ and real constant $c$, then how would one go about showing the following identity where $k$ is a fixed integer:

$\lim_{n\rightarrow \infty} \binom{n}{k}\frac{\binom{\binom{n-k}{2}}{N_c}}{\binom{\binom{n}{2}}{N_c}}=\frac{e^{-2kc}}{k!}.$

It feels like using Stirling's approximation would help but I can't quite figure out how...

I ask this question because I am currently trying to understand the paper in which Erdős initiated the study of the evolution of random graphs

P. Erdős and A. Rényi, On random graphs I, Publicationes Mathematicae Debrecen 6 (1959), pp.290–297, Erdős Project link.

where understanding this quantity is a key step in computing the probability that a graph on $n$ vertices with $N_c$ randomly chosen edges is completely connected.

1 Answers 1

3

The approximations still need to be justified, but here is the basic strategy. You begin by multiplying through by $k!$, to get

$ \begin{eqnarray*}{k!{n\choose k}}{{{n-k\choose 2}\choose N_c}\over{{n\choose 2}\choose N_c}} &=&n^k \prod_{i=0}^{k-1}\left(1-{i\over n}\right) \prod_{j={n-k\choose 2}+1}^{n\choose 2} \left(1-{N_c\over j}\right)\\ &\approx&n^k \prod_{j={n-k\choose 2}+1}^{n\choose 2} \left(1-{N_c\over j}\right).\end{eqnarray*} $

Taking the logarithm you get $k\log(n)+\sum_{j={n-k\choose 2}+1}^{n\choose 2} \log\left(1-{N_c\over j}\right) \approx k\log(n)-N_c\sum_{j={n-k\choose 2}+1}^{n\choose 2} {1\over j}. \tag 1$ Note that $\lim_{n\to\infty}N_c/j=0$. For $0\leq x\leq 1/2$ we have $0\leq -\log(1-x)-x\leq x^2$, so for large $n$ $ \left|\sum_{j={n-k\choose 2}+1}^{n\choose 2} \log\left(1-{N_c\over j}\right)+ N_c\sum_{j={n-k\choose 2}+1}^{n\choose 2} {1\over j}\right| \leq N_c^2\sum_{j={n-k\choose 2}+1}^{n\choose 2}{1\over j^2} \leq N_c^2{{n\choose 2}-{n-k\choose 2}\over{{n-k\choose 2}^2}}$ whose right hand side goes to zero as $n\to\infty$. This justifies (1).

Once you convince yourself that $\sum_{j={n-k\choose 2}+1}^{n\choose 2}{1\over j}\approx 2k/n$, and substitute the expression for $N_c$, the $k\log(n)$ terms on the right hand side of (1) cancel and you are left with $-2ck$. This gives the required result.