# Difference between revisions of "Random regular graph"

Line 2: | Line 2: | ||

==Properties of random regular graphs== | ==Properties of random regular graphs== | ||

− | As with more general [[random graph]]s, it is possible to prove that certain properties of random ''r''-regular graphs hold [[almost surely]]. In particular, a random ''r''-regular graph is almost surely [[connectivity (graph theory)|''r''-connected]].<ref>Bollobás, section 7.6: Random Regular Graphs</ref> In other words, although ''r''-regular graphs with connectivity less than ''r'' exist, the probability of selecting such a graph tends to 0 as ''n'' increases. | + | As with more general [[random graph]]s, it is possible to prove that certain properties of random ''r''-regular graphs hold [[almost surely]]. In particular, for <math> r \ge 3 </math>, a random ''r''-regular graph of large size is almost surely [[connectivity (graph theory)|''r''-connected]].<ref>Bollobás, section 7.6: Random Regular Graphs</ref> In other words, although ''r''-regular graphs with connectivity less than ''r'' exist, the probability of selecting such a graph tends to 0 as ''n'' increases. |

If <math>\epsilon</math> > 0 is a positive constant, and ''d'' is the least integer satisfying | If <math>\epsilon</math> > 0 is a positive constant, and ''d'' is the least integer satisfying |

## Latest revision as of 11:13, 10 December 2014

A **random r-regular graph** is a graph selected from , which denotes the probability space of all

*r*-regular graphs on

*n*vertices, where 3 ≤

*r*<

*n*and

*nr*is even.

^{[1]}It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.

## Properties of random regular graphs

As with more general random graphs, it is possible to prove that certain properties of random *r*-regular graphs hold almost surely. In particular, for , a random *r*-regular graph of large size is almost surely *r*-connected.^{[2]} In other words, although *r*-regular graphs with connectivity less than *r* exist, the probability of selecting such a graph tends to 0 as *n* increases.

If > 0 is a positive constant, and *d* is the least integer satisfying

then, almost surely, a random *r*-regular graph has diameter 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.^{[3]}

The distribution of the number of short cycles is also known: for fixed *m* ≥ 3, let *Y*_{3},*Y*_{4},…,*Y*_{m} be the number of cycles of lengths up to *m*. Then the *Y*_{i} are asymptotically independent Poisson random variables with means^{[4]}

## Algorithms for random regular graphs

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 multigraph. 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.^{[5]}

A refinement of this method was developed by Brendan McKay and Nicholas Wormald.^{[6]}

## References

- ↑ Béla Bollobás,
*Random Graphs*, 2nd edition, Cambridge University Press (2001), section 2.4: Random Regular Graphs - ↑ Bollobás, section 7.6: Random Regular Graphs
- ↑ Bollobás, section 10.3: The Diameter of Random Regular Graphs
- ↑ Bollobás, section 2.4: Random Regular Graphs (Corollary 2.19)
- ↑ N. Wormald, "Models of Random Regular Graphs," in
*Surveys in Combinatorics*, Cambridge University Press (1999), pp 239-298 - ↑ B. McKay and N. Wormald, "Uniform Generation of Random Regular Graphs of Moderate Degree,"
*Journal of Algorithms*, Vol. 11 (1990), pp 52-67: [1]