The random graph $\mathbf{G}_{n,p}$ contains a cycle a.a.s. when $p=\frac{1-\theta}{n}$, $\theta\ll 1$

Consider the binomial random graph $\mathbf{G}_{n,p}$ and let $P=P_{n,p}$ denote the probability that it contains a cycle. When $p=\frac{c}{n}$ for a constant $0<c<1$, there exists a constant $q=q(c)<1$ such that $P<q$ (for every $n$). That is, $P$ is asymptotically "bounded away" from $1$. This can be easily proved via FKG inequality, which shows $P\leq e^{-\mu}$ where $\mu$ is the expected number of cycles.

Now consider $p=\frac{1-\theta}{n}$, $\theta\ll 1$. I'm interested in a proof that $P\rightarrow 1$ as $n\rightarrow\infty$ in this case. I was trying Janson's inequality, which gives $1-P\leq e^{-\mu+\frac{\Delta}{2}}$. Here $\mu$ is as before: $$\mu = \sum_{C}\mathbb{P}(C\subseteq \mathbf{G}_{n,p})$$ (summing over all potential cycles) and $$\Delta = \sum_{C,C':E(C)\cap E(C')\neq\emptyset}\mathbb{P}(C,C'\subseteq \mathbf{G}_{n,p}).$$ Obviously we need $\Delta=o(\mu)$ but I find it problematic to prove here. The contribution to $\Delta$ from the summands of long cycles causes problems, since the huge amount of summands seems to "win" over the fact that each of them is now smaller. [I don't fully elaborate here so the question won't be too long, but you can ask me about what I know in the comments].

I couldn't find any source that deals with this question (elementarily), so either sources, ideas or suggestions of other approaches will be welcomed.

Solution 1:

A possible strategy: let $X_\ell$ be the number of $\ell$-cycles in $G(n,p)$. We can try to prove that for $p = \frac cn$, $0 < c< 1$, and for any constant $\ell$, the random variables $X_3, X_4, \dots, X_\ell$ asymptotically approach independent Poisson random variables as $n \to \infty$.

How might we do this? It is a variation of the method of moments for showing that a single random variable is asymptotically Poisson. There's two aspects to this method:

1. The probability theory: if we want to show that $X_3$ approaches a $\text{Poisson}(\frac{c^3}{6})$ random variable, it is enough to check that for any constant $k$, $\mathbb E[\binom{X_3}{k}] \to \frac{(c^3/6)^k}{k!}$ as $n \to \infty$: the value we'd expect from the $\text{Poisson}(\frac{c^3}{6})$ distribution.
2. The combinatorics: $\mathbb E[\binom{X_3}{k}]$ is counting the expected number of sets of $k$ $3$-cycles in $G(n,p)$. We get $\frac{(c^3/6)^k}{k!}$ because the main contribution is from sets of $k$ edge-disjoint $3$-cycles.

To prove that the random variables are independent in the limit, we should do a similar computation: for any constant $k_3, k_4, \dots, k_\ell$, verify that $$ \mathbb E\left[\binom{X_3}{k_3} \binom{X_4}{k_4} \cdots \binom{X_\ell}{k_\ell}\right] $$ approaches as $n \to \infty$ the value we'd expect from independent Poisson random variables. This expected value is counting the expected number of ways to choose $k_3$ $3$-cycles, $k_4$ $4$-cycles, ..., $k_\ell$ $\ell$-cycles from $G(n,p)$. This sounds daunting, but once again the main contribution is from sets of edge-disjoint (in fact, vertex-disjoint) cycles.

Anyway, once that is done, we have $$ \lim_{n \to \infty} \Pr[X_3 = X_4 = \dots = X_\ell = 0] = \exp\left(-\frac{c^3}{6} - \frac{c^4}{8} - \dots - \frac{c^{\ell}}{2\ell}\right). $$ This limit can be made arbitrarily close to $0$ by choosing a constant $c$ close enough to $1$, and a constant $\ell$ sufficiently large.

Let $P(c) = \lim_{n \to \infty} P_{n,c/n}$: the limiting probability that $G(n,\frac cn)$ contains a cycle. For any constant $\ell$, the limit above is a lower bound on $1-P(c)$. By monotonicity of having a cycle, we know that $P(c)$ is an increasing function of $c$. Since for $c<1$ but sufficiently close to $1$, we can make $P(c)$ arbitrarily close to $1$, then $P(1)$ can only be $1$.