I am going through a lecture on the hamiltonian cycle in random graphs:
http://web.mat.bham.ac.uk/combinatorics/LMS-EPSRC/MichaelLectures3_4.pdf
So its given:
But it seems they have not proved that the first part of proposition. So I am trying to prove it i.e. given $\frac{1}{n^2} \ll p = \frac{\ln n+\ln \ln n−\omega(n)}{n}$
, $\omega(n) \to \infty$ as $n \to \infty$, prove that whp there exists a vertex with degree $1$ in $G(n, p)$.
What I have tried:
The probability of having a vertex of degree $1$ is :
$$
\binom{n-1}1p^1(1-p)^{n-1-1}\;,
$$
And the expected number of vertices of degree $1$ is
$$
n\binom{n-1}1p^1(1-p)^{n-2}\ \sim n^2p e^{-np}
$$
After this, I believe we can substitute the value p in it:
$$
=n^2\frac{\ln n+\ln \ln n−\omega (n)}{n}e^{-np}= n(\ln n+\ln \ln n−\omega (n)) e^{-np}
$$
So can I assume that when $n \to \infty$ the above equation will tend to infinity? I am a bit confused about how to proceed from this. I am aware that I can use the second-moment method i.e. $P(X=0)\leq \frac{\mathrm{Var}[X]}{\mathbb E[X^2]}$ where $X$ is the number of vertices with degree $1$. But I am confused about how to find the $\mathbb E[X^2]$. Please could you help me to solve this? Thank you in advance.
Best Answer
The first thing we need to do is simplify $n^2p e^{-np}$ much more. We'll assume that $\omega(n) \ll \ln n$; for other values of $\omega(n)$, the claim we want follows by monotonicity.
For the $p$ on the outside, it's enough to know that $p \sim \frac{\ln n}{n}$ (which is where the assumption $\omega(n) \ll \ln n$ comes in), so that $n^2p \sim n \ln n$. The lower-order terms are important because $e^{-np} = e^{-\ln n} \cdot e^{-\ln \ln n} \cdot e^{\omega(n)} = \frac1{n \ln n} \cdot e^{\omega(n)}$. Altogether, we have $n^2p e^{-np} \sim e^{\omega(n)}$, which does go off to infinity.
Meanwhile, $X(X-1)$ counts ordered pairs of two different vertices of degree $1$. There are $n(n-1)$ possible pairs of vertices we could have, and the probability that they have degree $1$ is $p (1-p)^{2n-4} + (n-2)^2 p^2 (1-p)^{2n-3}$, depending on if they're adjacent to each other or to some other vertices. Multiplying these and ignoring lower-order terms, we get $$\mathbb E[X(X-1)] \sim n^4 p^2 (1-p)^{2n} \sim n^4 p^2 e^{-2np} \sim \mathbb E[X]^2.$$
This much is enough to be able to conclude that $\textrm{Var}[X] \ll \mathbb E[X^2]$, letting you apply the second moment method inequality you have in mind.