Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.