I am interested in a random graph $G\sim G(n,p)$. I know that if $p<<1/n$, then $G$ will be a forest. I happen to be interested in the boundary case where $p=c/n$, where $c<1$ is a constant. Does $G$ fail to be a forest with high probability in this case? Or is it still a forest some positive proportion of the time? Does it depend on $c$? References would be very appreciated as I don't know much about graph theory.
$\begingroup$
$\endgroup$
asked May 22, 2017 at 19:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
In this case, assuming $c\lt 1$ is independent of $n$, the number of cycles is asymptotically Poisson with constant mean $f(c)$. So asymptotically there is a constant nonzero probability $e^{-f(c)}$ that there are no cycles. With a rough calculation that needs checking, I got $$ e^{-f(c)} = \sqrt{1-c}\,\exp\bigl({{\textstyle\frac14}c(2+c)}\bigr).$$ You can see that the probability of being a forest goes to 0 as $c$ approaches 1 from below. The formula is not valid at all for $c\gt 1$.
Calculation (apply the word "asymptotically" to everything): the expected number of $k$-cycles is $E(C_k)=\frac1{2k}c^k$. The sum of $E(C_k)$ over $k\in[3,\infty]$ is $f(c) = -\frac12\ln(1-c)-\frac12c-\frac14c^2$ and so $e^{-f(c)}$ is the above.
answered May 23, 2017 at 6:13
-
$\begingroup$ Indeed, if I'm not wrong, for $c>1$ the graph contains a cycle w.h.p. (with probability 1): Luczak, T. (1991), Cycles in a random graph near the critical point. Random Struct. Alg., 2: 421–439. About general references for the OP, this book is great: Frieze, A., & Karoński, M. (2015).Introduction to Random Graphs. Cambridge University Press. It does not contain the above calculation, but provides the techniques for similar statements, and has an extensive bibliography. $\endgroup$ Commented May 23, 2017 at 11:42
-
$\begingroup$ I got $\frac 1 4 c (c+1) $ inside your exponential, actually.. $\endgroup$ Commented May 23, 2017 at 11:51
-
$\begingroup$ @LucaGhidelli I added some details so you can see where we differ. $\endgroup$ Commented May 23, 2017 at 13:21
-
$\begingroup$ You're totally right, I did the same calculation, only that for some reason at the end I subtracted $\frac 1 2 \binom c 2$. $\endgroup$ Commented May 23, 2017 at 13:37