In a Erdős-Rényi graph $G_{n,1/n}$, i.e., $n$ nodes and each arc is formed independently with probability $1/n$, what is the probability that it has at least one cycle?
I did refer to Erdős and Rényi's ON THE EVOLUTION OF RANDOM GRAPHS (https://www.renyi.hu/~p_erdos/1960-10.pdf). Although it talks about a non-directed graph, I believe the means should be the same. However, I don't really follow the proof of theorem 5b, in which they mention "an obvious sieve".
I can show that the number of $k$ cycles follows a Poisson distribution with expectation asymptotically $1/k$. Of course, here two cycles are not independent so that the Poisson distributions do not add. And all the literature I found stops with finding the expectation of the total number of cycles, which I know is $\sum 1/k$.
A simulation reveals that the probability is asymptotically 1, which I think is obvious since the dependence between cycles should be small. But I fail to find a way to give a precise proof. Can anyone give some hint?? Thanks!
Suppose $C_k$ is the number of k-cycles in $G(n,1/n)$. It turns out that $C_k \stackrel{d}\to \operatorname{Poi}(\frac1{2k})$. Even to prove this simple fact, the usual CLT type argument will not work as we have dependencies even between cycles of same length. A way to prove this is to use Chen-Stein Method or to show that factorial moments converge.
However, using Chen-Stein Method, it is also possible to show that any finite linear combinations of $C_j$'s has poissonian limit. That is
$$\sum_{j=3}^k a_jC_j \stackrel{d}\to \operatorname{Poi}\left(\sum_{j=3}^k\frac{a_j}{2j}\right)$$
A proof of this result is available in the lecture notes of Bordenave. See here (Page 30).
Using this one can show that $$\begin{aligned} P(\mbox{no cycle}) & \le P(\mbox{no cycle of length at least k}) \\ & = P(C_1+C_2+\cdots+C_k=0)=\exp(-\sum_{j=3}^k \frac1{2j}) \to 0 \end{aligned}$$