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?