Erdős–Rényi random graphs — reproducing 2 inequalities

Question

In Erdős and Renyi's 1959 paper On random graphs I , I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}.

Eq.\eqref{1} is: $$ P \le \sum_{s=2}^{\log \log n}{n \choose s} \left[\sum_{r=1}^{{s \choose 2}} { {s \choose 2} \choose r} {\frac {\dbinom{n-s \choose 2} {N_{c}-r}} {\dbinom{n \choose 2} {N_{c}}} }\right] \label{1}\tag{19} $$

where $n$ is the total number of nodes in the graph, and $$N_c = \left\lfloor{\frac 1 2} n \log n +cn\right\rfloor$$ where $c$ is a real number. $P$ is the probability of a certain class of graphs occurring under constraints provided in the paper (details not needed here). The summation variable $r$ represents the number of edges in a subset of $s$ nodes, and so $r$ is summing over all such possible (nonzero) values, from 1 to its maximum value which is the combination $C(s,2)$. Ultimately, the limit $n \rightarrow \infty$ will be needed since the asymptotic behavior is being investigated.

From Eq.\eqref{1} I'd like to reproduce Eq.\eqref{2} in the paper, which is:

$$P \le {\frac {\log n} n} \sum_{s=2}^{\log \log n} {\frac {2^{s \choose 2} e^{-2sc}} {s!}} \le {\frac {e^{e^{-2c}}e^{{\frac 1 2}(\log \log n)^2}} n}. \label{2}\tag{20}$$

A) Going from \eqref{1} to the middle expression in \eqref{2}

In \eqref{1}, since we need an upper bound, I proceeded by replacing the second combination term in the $r$ sum (i.e. the one in the numerator) by its maximum value and factoring it out of the sum, and starting the sum from 0, which yields: $$\sum_{r=1}^{{s \choose 2}} { {s \choose 2} \choose r} {\dbinom{n-s \choose 2} {N_{c}-r}} \le \max_{r}{\dbinom{n-s \choose 2} {N_{c}-r}}\sum_{r=0}^{{s \choose 2}} { {s \choose 2} \choose r} = \max_{r}{\dbinom{n-s \choose 2} {N_{c}-r}}2^{\binom{s}{2}} $$ where the equality follows from a standard binomial sum, and reproduces the factor $2^{s \choose 2}$ which is in the middle expression in \eqref{2}. I have tried other approximations, but only this one readily leads me to the factor $2^{s \choose 2}$. For the $\max$, the upper argument varies as $n^2$, the lower as $N_{c} \sim n \log n$, so as $n$ increases without bound the true maximum of this combinatorial term (obtained if the lower arg is roughly half the upper) cannot be obtained, but it comes closest to the maximum when $r=0$ (making the lower arg as large as possible, yet still less than half the upper), so \eqref{1} now becomes:

$$P \le {\frac {1} {\dbinom{n \choose 2} {N_{c}}} }\sum_{s=2}^{\log \log n}{n \choose s} 2^{{s}\choose {2}} {\dbinom{n-s \choose 2} {N_{c}}}. \label{3}\tag{19${}'$} $$ From here, I'm not reproducing the term $\exp(-2sc)$ in \eqref{2}: The factor of $c$ in the exponential is in the definition of $N_{c}$ (see above), but I find that the exponentials from applying Stirling's approximation to \eqref{3} contain terms of the form $\exp(-nc)$ (with $n$ instead of $s$) but they cancel (numerator and denominator). The other (non-exponential) terms from Stirling appear to cancel for large $n$. I'm also not obtaining the factor of $(\log n)/n$ in \eqref{2}. Would appreciate any thoughts on getting to the middle expression of \eqref{2}.

B) Going from the middle expression in \eqref{2} to the rightmost expression in \eqref{2}

Most of the right side is reproducible as follows. Considering the following factor (middle expression of \eqref{2}): $$2^{s \choose 2} \lt e^{s \choose 2} = e^{\frac {s(s-1)}{2}} \lt e^{\frac {s^2}{2}}$$

and evaluating $s$ in this expression at its max value of $\log \log n$ produces one of the terms on the right of \eqref{2}. And carrying out the sum on the remaining $s$-dependent factors, $\exp(-2sc)/s!$, and summing from 0 to $\infty$, yields $\exp (\exp(-2c) )$, also on the right side of \eqref{2}. But I'm not capturing the factor that cancels the $\log n$ factor.

Any thoughts greatly appreciated.

I should add that there is another post on (a slightly different set of) Erdős–Rényi inequalities, but it doesn't address the form of the upper bounds. It looks at ratios of successive terms in the series and part of the upper bound (taken as given) actually drops out. I'm asking about the derivation of the form itself.

Answer 1

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$We are going to deduce from \eqref{1} a bound better than the ultimate bound in \eqref{2}. Actually, we are going to obtain the exact asymptotic of the upper bound in \eqref{1}.

(In particular, it follows that the ultimate bound in \eqref{2} is not optimal. Already for this reason, it seems hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get \eqref{2} from \eqref{1}.)

To begin our consideration, note that the upper bound on $P$ in \eqref{1} is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

---

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}