9
$\begingroup$

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:

$$\binom{n}{s}\frac{\displaystyle\binom{\binom{n}{2}-s(n-s)}{N_c}}{\displaystyle\binom{\binom{n}{2}}{N_c}}\le\frac{e^{(3-2c)s}}{s!}$$

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!

  • 0
    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.2012-01-05
  • 0
    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.2012-01-05
  • 0
    Had a brief look, couldn't find it, maybe I was confusing it with something else. Sorry.2012-01-05
  • 0
    No worries --- there are so many questions mentioning binomial coefficients, it's definitely possible it's out there somewhere! Thanks for having a look.2012-01-05
  • 2
    @Gerry Are you remembering [this post](http://math.stackexchange.com/revisions/91298/4)? Unfortunately [that question](http://math.stackexchange.com/questions/91298/binomial-inequality) has been modified several times since.2012-01-06
  • 0
    @Srivatsan, yes, I think that's the one I was thinking of. Thanks.2012-01-06

1 Answers 1

3

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{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$ is replaced by $n-s$.

  • 0
    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?2012-01-06
  • 0
    Ahh --- I see where the bound on the product comes from now. Feeling a bit silly for not noticing that.2012-01-06