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.
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?