I am stuck on a detail of the proof of the very sharp threshold for connectivity in Erdős-Rényi graphs---this question corresponds to Theorem 9 in Cahpter VII of "Random Graphs" by Bollobás.
We are given $\omega (n)$ such that the following hold:
- $\omega (n) \to \infty $ as $n\to \infty $
- $\omega (n) \le \log \log n$
- $n$ large enough so that $\omega (n)\ge 10.$
In the book, it is claimed that the following bound holds:
$\displaystyle\sum_{1\le k \le n^{3/4} } e^{(1-\omega (n))k}k^{-k}e^{2k^2 (\log n ) / n} \le 3 e^{-\omega (n)}.$
I don't see which of the assumptions stated above are necessary for this bound to work (incidentally, the rest of the proof seems ok to me.) Any advice you might have will be most appreciated.
We can begin by pulling out a power of $k$: $$ e^{(1 - \omega(n))k} k^{-k} e^{k^2 \log n/n} = \left( e^{1 - \omega(n)} k^{-1} e^{k \log n/n}\right)^k. $$ Here, for $1 \le k \le n^{3/4}$, the factors $k^{-1} e^{k \log n/n}$ can be ignored for the following reasons:
(Here, we used the second and third assumptions to conclude that $\log \log n \ge 10$, so $n$ is large.)
So we have $$ \left( e^{1 - \omega(n)} k^{-1} e^{k \log n/n}\right)^k \le \left(1.001 e^{1 - \omega(n)}\right)^k. $$ Now the sum over $k \le n^{3/4}$ can be bounded by the sum over all positive integers $k$, which is a geometric series: $$ \sum_{k=1}^{n^{3/4}} \left(1.001 e^{1 - \omega(n)}\right)^k \le \sum_{k=1}^\infty \left(1.001 e^{1 - \omega(n)}\right)^k = \frac{1.001 e^{1-\omega(n)}}{1 - 1.001 e^{1 - \omega(n)}}. $$ Pulling out the $e^{-\omega(n)}$ we wanted, we are left with $$ \frac{1.001 e}{1 - 1.001 e^{1 - \omega(n)}} \cdot e^{-\omega(n)} \le \frac{1.001 e}{1 - 1.001 e^{-9}} \cdot e^{-\omega(n)} $$ and the constant factor here is less than $3$; it is more or less $e$.
(In the last step, we use the $\omega(n) \ge 10$ assumption again.)