Please refer to this, it is Erdos-Renyi 1959 paper 1 on Random Graphs. I am currently working on this, but I am stuck on the fifth page, where they use two estimates. More specifically, here's the question:
Define $N_c=[\dfrac{1}{2}n\log n+cn]$ where $[.]$ denotes the greatest integer function, and $c$ is any arbitrary fixed real constant. Also, let $M={n\choose 2}$.
Then prove, for large $n$, the following inequalities:
$$\large{n\choose s}\dfrac{{{M - s(n-s)}\choose N_c}}{M\choose N_c}\leq \dfrac{e^{(3-2c)s}}{s!}\space\space\space\space\text{for } s\leq\dfrac{n}{2}$$
and $$\large{n\choose s}\dfrac{{{M - s(n-s)}\choose N_c}}{M\choose N_c}\leq \dfrac{e^{(3-2c)(n-s)}}{(n-s)!}\space\space\space\space\text{for } s\geq\dfrac{n}{2}$$
Here, $s$ is a positive integer such that $s<n-\dfrac{2N_c}{n}$.
I admit, these inequalities are a bit strange. But, I am convinced that these are simply estimates. The paper I am referring to, simply says, "by some elementary estimations, we get...", but do not mention how they get these.
I "believe" Stirling's Approximation has been used, repeatedly, along with some other crude estimates. I am particularly having some problem figuring out how those estimates have been used.
I observe that for large $n$, by applying Stirling's Approximation, $${n\choose s}\sim \dfrac{e^{-s}n^{n+1/2}}{(n-s)^{n-s+1/2}s!}---(1)$$
$${{M-s(n-s)}\choose N_c}\sim \dfrac{e^{-N_c}{(M-s(n-s))}^{M-s(n-s)+1/2}}{{(M-s(n-s)-N_c)}^{M-s(n-s)-N_c+1/2}N_c!}---(2)$$
$${M\choose N_c}\sim \dfrac{e^{-N_c}M^{M+1/2}}{(M-N_c)^{M-N_c+1/2}}---(3)$$
Then, $(1)\times (2)/(3)$ is something, whose bound I want to make equal to the bounds given.
But things are getting too complicated by now. Please remember that $M={n\choose 2}$. Am I on the right track? I tried to simplify these but things aren't working in my favor.
There are other inequalities in the paper with "similar" flavour, hence I believe that if I can understand how these inequalities are solved, then I can understand how the other inequalities have been deduced. I have been stuck on it for quite some time now, so some help is definitely more than appreciated.