Random regular graph

A random r-regular graph is a graph selected from ${\displaystyle {\mathcal {G}}_{n,r}}$, which denotes the probability space of all r-regular graphs on ${\displaystyle n}$ vertices, where ${\displaystyle 3\leq r<n}$ and ${\displaystyle 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 ${\displaystyle m}$–regular graphs hold asymptotically almost surely. In particular, for ${\displaystyle r\geq 3}$, a random r-regular graph of large size is asymptotically almost surely r-connected.^[2] In other words, although ${\displaystyle r}$–regular graphs with connectivity less than ${\displaystyle r}$ exist, the probability of selecting such a graph tends to 0 as ${\displaystyle n}$ increases.

If ${\displaystyle \epsilon >0}$ is a positive constant, and ${\displaystyle d}$ is the least integer satisfying

${\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}$

then, asymptotically 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 ${\displaystyle m\geq 3}$, let ${\displaystyle Y_{3},Y_{4},...Y_{m}}$ be the number of cycles of lengths up to ${\displaystyle m}$. Then the ${\displaystyle Y_{i}}$are asymptotically independent Poisson random variables with means^[4]

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

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