7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ BTW, Vivek, you should accept answers if they do answer the question as posed. $\endgroup$ Mar 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$ Mar 2, 2017 at 20:40

1 Answer 1

15
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The link you offered is not found now. $\endgroup$
    – Jxb
    Jan 8 at 12:02
  • $\begingroup$ how to prove the existence of $d$-regular expander graph with probabilistic method? $\endgroup$
    – Jxb
    Jan 8 at 12:12
  • 1
    $\begingroup$ See my answer here: mathoverflow.net/a/132509/34591 $\endgroup$ Jan 12 at 12:55
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.