Random regular graph

<h2 id="properties-of-random-regular-graphs">Properties of random regular graphs</h2>
As with more general <a href="/facts/Random_graph/gfQhq1Sz">random graphs</a>, it is possible to prove that certain properties of random 
 
 
 
 m
 
 
 {\displaystyle m}
 
–regular graphs hold <a href="/facts/Almost_surely/fWaxzpBA">asymptotically almost surely</a>. In particular, for 
 
 
 
 r
 ≥
 3
 
 
 {\displaystyle r\geq 3}
 
, a random r-regular graph of large size is asymptotically almost surely <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">r-connected</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> In other words, although 
 
 
 
 r
 
 
 {\displaystyle r}
 
–regular graphs with connectivity less than 
 
 
 
 r
 
 
 {\displaystyle r}
 
 exist, the probability of selecting such a graph tends to 0 as 
 
 
 
 n
 
 
 {\displaystyle n}
 
 increases. 
If 
 
 
 
 ϵ
 >
 0
 
 
 {\displaystyle \epsilon >0}
 
 is a positive constant, and 
 
 
 
 d
 
 
 {\displaystyle d}
 
 is the least integer satisfying

 
 
 
 (
 r
 −
 1
 
 )
 
 d
 −
 1
 
 
 ≥
 (
 2
 +
 ϵ
 )
 r
 n
 ln
 ⁡
 n
 
 
 {\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}

then, asymptotically almost surely, a random r-regular graph has <a href="/facts/Diameter_(graph_theory)/EmQFKvqa">diameter</a> at most d. There is also a (more complex) lower bound on the diameter of r-regular graphs, so that almost all r-regular graphs (of the same size) have almost the same diameter.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
The distribution of the number of short cycles is also known: for fixed 
 
 
 
 m
 ≥
 3
 
 
 {\displaystyle m\geq 3}
 
, let 
 
 
 
 
 Y
 
 3
 
 
 ,
 
 Y
 
 4
 
 
 ,
 .
 .
 .
 
 Y
 
 m
 
 
 
 
 {\displaystyle Y_{3},Y_{4},...Y_{m}}
 
 be the number of cycles of lengths up to 
 
 
 
 m
 
 
 {\displaystyle m}
 
. Then the 
 
 
 
 
 Y
 
 i
 
 
 
 
 {\displaystyle Y_{i}}
 
are asymptotically independent Poisson random variables with means<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

 
 
 
 
 λ
 
 i
 
 
 =
 
 
 
 (
 r
 −
 1
 
 )
 
 i
 
 
 
 
 2
 i
 
 
 
 
 
 {\displaystyle \lambda _{i}={\frac {(r-1)^{i}}{2i}}}

<h2 id="algorithms-for-random-regular-graphs">Algorithms for random regular graphs</h2>
It is non-trivial to implement the random selection of r-regular graphs efficiently and in an unbiased way, since most graphs are not regular. The pairing model (also configuration model) is a method which takes nr points, and partitions them into n buckets with r points in each of them. Taking a random matching of the nr points, and then contracting the r points in each bucket into a single vertex, yields an r-regular graph or <a href="/facts/Multigraph/udmS0Cp0">multigraph</a>. If this object has no multiple edges or loops (i.e. it is a graph), then it is the required result. If not, a restart is required.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
A refinement of this method was developed by <a href="/facts/Brendan_McKay_(mathematician)/zEvgN64q">Brendan McKay</a> and Nicholas Wormald.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Béla Bollobás, Random Graphs, 2nd edition, Cambridge University Press (2001), section 2.4: Random Regular Graphs <a href="/wiki/B%C3%A9la_Bollob%C3%A1s" target="_blank">/wiki/B%C3%A9la_Bollob%C3%A1s</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bollobás, section 7.6: Random Regular Graphs <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bollobás, section 10.3: The Diameter of Random Regular Graphs <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bollobás, section 2.4: Random Regular Graphs (Corollary 2.19) <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">N. Wormald, "Models of Random Regular Graphs," in Surveys in Combinatorics, Cambridge University Press (1999), pp 239-298 <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">B. McKay and N. Wormald, "Uniform Generation of Random Regular Graphs of Moderate Degree," Journal of Algorithms, Vol. 11 (1990), pp 52-67: [1] <a href="http://cs.anu.edu.au/~bdm/papers/RandRegGen.pdf" target="_blank">http://cs.anu.edu.au/~bdm/papers/RandRegGen.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Random regular graph open-in-new

Random regular graph