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[]