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

combinatoricsgraph theoryprobabilityrandom-graphs

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, there exists a constant $$q=q(c)<1$$ such that $$P (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.

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