Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959

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