Please refer to [this](http://snap.stanford.edu/class/cs224w-readings/erdos59random.pdf), 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.



Proofs of inequalities used by Erdos-Renyi in their Random Graphs Paper 1
Let $n$ be large enough so that $N\_c=\lfloor\frac{1}{2}n\ln n+cn\rfloor\ge0$ (even when $c<0$). On the other hand, the condition that $s$ is a positive integer such that $s<n-\dfrac{2N\_c}{n}$ yields $N\_c\le M$. Thus, $N\_c\in\{0,\dots,M\}$, and so, the left-hand side of your inequalities is well defined -- assuming, by the standard convention, that $\binom{M - s(n-s)}N=0$ if $M - s(n-s)<N$. 


Let $N:=N\_c$, so that $c\le c\_N:=-\frac12\ln n+\frac{N+1}n$. So, to prove the inequalities in question, it suffices to show that 
$$(1)\qquad r\_N:=r\_{N,t}:=\binom nt
\dfrac{\binom{M - t(n-t)}N}{\binom{M}N}\Big/\dfrac{e^{(3-2c\_N)t}}{t!}\le1 
$$
for $N\in\{0,\dots,M\}$, 
where $t:=s\wedge(n-s)$ -- and $c$ is gone. 
If $M - t(n-t)<N$ then $r\_N=0$, and hence $(1)$ is trivial. 
If $M - t(n-t)\ge N$ and $N\in\{0,\dots,M-1\}$ then 
$$\frac{r\_{N+1}}{r\_N}=\frac{M-N-t(n-t)}{M-N}\,e^{2/n}
\le\frac{M-t(n-t)}{M}\,e^{2/n}\le\frac{M-1(n-1)}{M}\,e^{2/n}=(1-2/n)e^{2/n}<1, 
$$
so that $r\_0\ge r\_1\ge \cdots\ge r\_M$. Thus, it suffices to prove $(1)$ for $N=0$. 
But 
$$r\_{0,t} 
=\frac{n!}{(n-t)!} \Big(\frac{e^{2/n-3}}{n}\Big)^t 
$$
and 
$$\frac{r\_{0,t+1}}{r\_{0,t}}=\frac{n-t}n\,e^{2/n-3}\le1, 
$$
so that $r\_{0,t}\le r\_{0,0}=1$, which completes the proof. In fact, it is seen that $3$ can be replaced in $(1)$ (and hence in the original inequalities in question) by the smaller (and hence better) value $2/n$.


