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?