An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? In particular will this be connected for some degree less than $\log n$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ BTW, Vivek, you should accept answers if they do answer the question as posed. $\endgroup$– Sasho NikolovMar 2, 2017 at 15:15
-
$\begingroup$ I will to read/glance the paper and then accept the answer. Thanks for letting me know though! $\endgroup$– Vivek BagariaMar 2, 2017 at 20:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.
-
-
$\begingroup$ how to prove the existence of $d$-regular expander graph with probabilistic method? $\endgroup$– JxbJan 8 at 12:12
-
1
-
1$\begingroup$ @Jxb I noticed that the link in the MO answer was broken. Sorry about that - I just have fixed it. $\endgroup$ Jan 14 at 18:11