I'm working my way through an Erdős paper from the sixties and some of the elementary bounds he claims seem to be just beyond my reach. The expression looks horrendous but maybe there is a clever simplification? In the following expression, $n$ and $s$ are positive integers and $c$ is an arbitrary real constant, why is it true (for $n\gg0$) that $$ \binom{n}{s}\frac{\binom{\binom{n}{2}-s(n-s)}{\lfloor \frac{1}{2}n \log n + cn\rfloor}}{\binom{\binom{n}{2}}{\lfloor \frac{1}{2}n \log n + cn\rfloor}}\leq\frac{e^{(3-2c)s}}{s!} \text{ when } s\leq n/2? $$

According to Erdős, this should be elementary. I asked a similar question here Evaluating a limit involving binomial coefficients. but can't seem to easily deduce this other bound from the technique given there.

If you're curious, this comes up in this paper http://www.renyi.hu/~p_erdos/1959-11.pdf where the quantity is related to threshold functions of random graphs.

  • 1
    $\begingroup$ This demonstrates the importance of proving every statement which is claimed. While this particular proof could be wrong (though perhaps fixable), the results of the paper are certainly correct, though usually proved in the $G(n,p)$ model. $\endgroup$ – Yuval Filmus Apr 24 '12 at 4:31

I think there may be a problem with the bound when $s$ grows linearly with $n$, in particular, when $s=n/2$. But you should double check my argument to be sure.

Following the authors's notation, let $N_c=\lfloor {1\over 2}n\log(n)+cn\rfloor$.

Their bound is equivalent to $$\left[{s!{n\choose s}} {\displaystyle{{n\choose 2}-s(n-s)\choose N_c}\over \displaystyle{{n\choose 2}\choose N_c}}\right]^{1/s}\leq e^{3-2c},\tag1$$ or in product form $$ \prod_{i=0}^{s-1}\left(n- i\right)^{1/s} \prod_{j={n\choose 2}-s(n-s)+1}^{n\choose 2} \left(1-{N_c\over j}\right)^{1/s}\leq e^{3-2c}.\tag2$$ The authors say that (1) holds for sufficiently large $n$.

I will assume that $n$ is large enough so that $$0\leq N_c\leq {1\over 3}\left[{n\choose2}-(n/2)^2\right]. \tag3$$ This is possible since $cn$ grows like a multiple of $n$, $N_c$ grows like a multiple of $n\log(n)$, while ${n\choose2}-(n/2)^2$ grows like a multiple of $n^2$.

We begin with the factor $ \prod_{i=0}^{s-1}\left(n-i\right)^{1/s}$, and lower bound its logarithm to obtain: $${1\over s}\sum_{i=0}^{s-1}\log\left(n-i\right) \geq \log(n/2)=\log(n)-\log(2).\tag4$$

The logarithm of the other factor on the left hand side of (2) is $${1\over s}\sum_{j={n\choose 2}-s(n-s)+1}^{n\choose 2} \log\left(1-{N_c\over j}\right)\tag5 $$ From the inequality $\log(1-x)\geq -4x/3$ for $0\leq x\leq 1/3$, and assumption (3) we see that $$\begin{eqnarray*} {1\over s}\sum_{j={n\choose 2}-s(n-s)+1}^{n\choose 2} \log\left(1-{N_c\over j}\right) &\geq& {-4 N_c\over 3s}\sum_{j={n\choose 2}-s(n-s)+1}^{n\choose 2} {1\over j}\\[5pt] &\geq&{-4 N_c\over 3s}\int_{{n\choose 2}-s(n-s)}^{n\choose 2} {dt\over t} \\[5pt] &=& {-4 N_c\over 3s}\log\left({{n\choose 2} \over {n\choose 2}-s(n-s)} \right)\\ \end{eqnarray*} $$

Substituting $-N_c\geq -({1\over 2}n\log(n)+cn)$ and $s=n/2$ gives a lower bound of $$-(\log(n)+2c)\, {4\over 3}\log\left({2(n-1)\over n-2}\right) \approx -\log(n)\, {4\over 3}\log(2)-{8c\over 3}\log(2).\tag6$$

Since ${4\over 3}\log(2)\approx .9242$, by adding (4) and (6) we find that the left hand side of (1) grows at least like $n^{.0758}$ as $n$ goes to infinity, so the inequality in (1) is false.

Have I made a mistake somewhere?

  • $\begingroup$ Now that's rather troubling. $\endgroup$ – Maxime Apr 24 '12 at 2:12
  • $\begingroup$ I agree. I really hope that I made a mistake, but I can't find it. $\endgroup$ – user940 Apr 24 '12 at 2:21
  • $\begingroup$ Have you tried computing the sides for various values of n, s, and c? $\endgroup$ – marty cohen Apr 24 '12 at 5:44
  • 2
    $\begingroup$ You're right @ByronSchmuland it turns out this is a (not so) well known error in this foundational paper. Good eye for sniffing it out! $\endgroup$ – Maxime Apr 24 '12 at 22:20

The bound is indeed false as stated but the lemma which relied on this inequality can be proven far more effectively in the realm of binomial as opposed to uniform random graphs as kindly pointed out by Yuval.

Check out the fourth page of the following 1997 paper:


On the other hand, the bound can be corrected by changing the requirement that $s\leq \frac{n}{2}$ to $s\leq \frac{n}{\log n}$, this appears as exercise $7.15$ of the book Random Graphs by Bollobás where it is indicated that Godehardt and Steinbach used this to correct Erdős' original lemma.

  • $\begingroup$ Interesting! Thanks for the link. $\endgroup$ – user940 Apr 24 '12 at 22:45

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.