According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as $n\rightarrow\infty$, where $\mu_i=\frac{(d-1)^{c_i}}{2c_i}$. So it seems that as $d$ gets larger, $\mu_i$ also gets larger and thus $P$ gets smaller. But this looks very counterintuitive, since as $d$ gets larger there are more edges in the graph, so the probability of having a cycle of any fixed length should increase. What am I missing?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ @FedorPetrov Doesn't it only get denser if you fix $n$ and increase $d$? You're only adding more edges. $\endgroup$– AlexiSep 4, 2015 at 17:57
-
$\begingroup$ Ah, I misread what goes larger. Then answer below explains everything. $\endgroup$– Fedor PetrovSep 4, 2015 at 18:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I can't comment, but $P$ is the probability that there are NO cycles of those lengths. So this probability goes down. Your intuition holds.