Elementary bound of binomial coefficient 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.
 A: 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?
A: 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:
http://main2.amu.edu.pl/~rucinski/papers/45.pdf
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.
