2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This is beautiful! Thank you very much! I also learnt, through your answer, some important tricks. $\endgroup$ Dec 24, 2015 at 3:02
  • $\begingroup$ However, I have one little doubt. We are looking at "large" $n$, so is putting $N=0$ a legal move? $\endgroup$ Dec 24, 2015 at 3:04
  • 1
    $\begingroup$ Yes, this move is legal. I have added the corresponding details to the proof. The values of $n$ do not play any role in this proof, except that they have to be large enough to ensure that $N_c=\lfloor\frac{1}{2}n\ln n+cn\rfloor\ge0$ (even when $c<0$). Note also that, if $N_c<0$, then the left-hand side of your inequalities is ill-defined. $\endgroup$ Dec 24, 2015 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.