Skip to main content
added 249 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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.

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

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.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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