I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I". In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial coefficients:


where $N_c = [\frac{1}{2}n\log{n} + c n]$, $s\le n/2$ and $n > n_0$ for some $n_0$, and $[x]$ denotes the largest integer less than or equal to $x$. (Equation 15 gives a corresponding expression for the case $s \ge n/2$.)

After spending some time playing around with Stirling's approximation and bounds such as $\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \frac{n^k}{k!} \le \left(\frac{n \cdot e}{k}\right)^k$, I don't feel that I'm any closer to understanding where this bound comes from.

It seems like there ought to be a fairly straightforward procedure for obtaining such bounds, given that the authors didn't feel any need to elaborate. I'd be very grateful for any pointers on how to proceed!

  • $\begingroup$ Question seems very familiar. Was it raised before here, or at MathOverflow? If so, a link to the earlier discussion would be a welcome addition. $\endgroup$ – Gerry Myerson Jan 5 '12 at 22:41
  • $\begingroup$ Hi @GerryMyerson, I did have a look for other relevant mathoverflow and math.stackexchange questions, but didn't find anything that quite fit the bill. I'd definitely be interested in any relevant discussions. $\endgroup$ – duncanm Jan 5 '12 at 23:05
  • $\begingroup$ Had a brief look, couldn't find it, maybe I was confusing it with something else. Sorry. $\endgroup$ – Gerry Myerson Jan 5 '12 at 23:13
  • $\begingroup$ No worries --- there are so many questions mentioning binomial coefficients, it's definitely possible it's out there somewhere! Thanks for having a look. $\endgroup$ – duncanm Jan 5 '12 at 23:16
  • 2
    $\begingroup$ @Gerry Are you remembering this post? Unfortunately that question has been modified several times since. $\endgroup$ – Srivatsan Jan 6 '12 at 3:39

If $s$ is not too large, the inequality is correct. This is because the quotient of binomial coefficients is $$ \prod_{0\le i<N_c} \frac{{n\choose 2}-s(n-s)-i}{{n\choose 2}-i} = \prod_{0\le i<N_c} \left(1-\frac{s(n-s)}{{n\choose 2}-i}\right) \le \exp -\frac{2s(n-s)}{n^2} N_c, $$ so it is enough to have $$ n^s \exp -\frac{2s(n-s)}{n^2} N_c \le e^{(3-2c)s}, $$ or, taking logarithms, $$ - \frac{2s(n-s)}{n^2} N_c +s\log n\le (3-2c)s. $$ Now, $N_c=\frac{1}{2}n\log n+cn-\theta$, for some $0\le\theta<1$, and inserting this into this last inequality cancels the terms $s\log n$ and $-2cs$, leaving $$ \frac{2s(n-s)}{n^2}\theta +\frac{2s^2}{n^2}(\frac{1}{2}n\log n+cn)\le 3s, $$ which is true if we require that $s\le n/\log n$ and that $n$ be sufficiently large.

If $s=\Omega(n)$, the inequality will not hold. Set $s:=\lfloor n\delta \rfloor$, fix $\delta\in(0,\frac{1}{2}]$ and $c$, and let $n$ become large. Look at the logarithms of each side. The quotient of binomial coefficients on the left-hand side will give $$N_c \log(1-s(n-s){n\choose 2}^{-1})+O((\log n)^2)=\frac{1}{2}(n\log n) \log(1-2\delta(1-\delta)) + O(n),$$ while $\log {n\choose s}=O(n)$. On the right-hand side, the logarithm of $1/s!$ is $-\delta n \log n + O(n)$, and $\log e^{(3-2c)s}$ is $O(n)$. Therefore, if the inequality were true, we would have $$ \frac{1}{2}( n\log n) \log(1-2\delta(1-\delta))+O(n)\le -\delta n\log n+O(n), $$ but since $\frac{1}{2}\log (1-2\delta(1-\delta))>-\delta$ for all $\delta$ in $(0,\frac{1}{2}]$, this is false for large enough $n$.

The failure of the inequality for large $s$ is not a problem for the Erdős-Rényi paper. This is because the use of this inequality (numbered (14) in the paper) is to bound the sum of the left-hand side of (14) as $s$ varies between some lower bound and $n/2$. However, the quotient of binomial coefficients is decreasing over $0\le s\le n/2$, so if we set $s_0:=n/\log n$ and sum the left-hand side of (14) over $s_0\le s\le n/2$, the result will be no more than $$ 2^n \left.\binom{\binom{n}{2}-\lceil s_0\rceil(n-\lceil s_0\rceil)}{N_c}\right/\binom{\binom{n}{2}}{N_c} \le 2^n \exp -\frac{2s_0(n-s_0)}{n^2} N_c, $$ and taking the logarithm of the right-hand side gives $$ n\log 2 - \frac{2s_0(n-s_0)}{n^2} (\frac{1}{2}n\log n+cn-\theta). $$ However, if we fix $c$, this is $-n(1-\log 2)+O(n/\log n)$, which approaches $-\infty$ as $n$ becomes large. Therefore, the right-hand side of the inequality (13) in the paper may be split into four pieces: (1) $M<s<n/\log n$, (2) $n/\log n\le s\le n/2$, (3) $n/2< s\le n-(n/\log n)$, and (4) $n-(n/\log n)<s<n-2N_c/n$. Pieces (1) and (4) can be shown to be small by (14) and (15), (2) is small by the estimate immediately above, and (3) can also be shown to be small by the above estimate as the sum of the left-hand side of (14) does not change when $s$ is replaced by $n-s$.

  • $\begingroup$ thanks for your response. Could you expand on a few points for me? In particular: (i) How do you get the bound $\exp{(-2 s(n-s) N_c/n^2)}$ for the quotient of binomial coefficients? and (ii) in the original article, there don't appear to be constraints on $s$ that are as strong as $s \le n/\log{n}$; is that constraint tight? $\endgroup$ – duncanm Jan 6 '12 at 10:45
  • $\begingroup$ Ahh --- I see where the bound on the product comes from now. Feeling a bit silly for not noticing that. $\endgroup$ – duncanm Jan 6 '12 at 17:32

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.