Random regular graph

A random r-regular graph is a graph selected from ${\mathcal {G}}_{n,r}$, which denotes the probability space of all r-regular graphs on n vertices, where 3 ≤ r < n and nr is even. It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold.

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, a random r-regular graph is almost surely r-connected. 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 $\epsilon$ > 0 is a positive constant, and d is the least integer satisfying

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

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 have almost the same diameter.

The distribution of the number of short cycles is also known: for fixed m \ge 2, let Y₃,Y₄,…,Y_m be the number of cycles of lengths up to m. Then the Y_i are asymptotically independent Poisson random variables with means $\lambda _{i}={\frac {(r-1)^{i}}{2i}}$.

Algorithms for Random Regular Graphs

Pairing Model, also called Configuration Model, is one of the most commonly used model to generate regular graphs uniformly. Suppose we want to generate graphs from ${\mathcal {G}}_{n,d}$, where d is a constant, the pairing model is described as follows.

Consider a set of nd points, where nd is even, and partition them into n buckets with d points in each of them. We take a random matching of the nd points, and then contract the d points in each bucket into a single vertex. The resulting graph is a d-regular multigraph on n vertices.

Let ${\mathcal {P}}_{n,d}$ denote the probability space of random d-regular multigraphs generated by the pairing model as described above. Every graph in ${\mathcal {G}}_{n,d}$ corresponds to (d!)^n copies in ${\mathcal {P}}_{n,d}$, So all simple graphs, namely, graphs without loops and multiple edges, in ${\mathcal {P}}_{n,d}$ occur uniformly at random.

Properties of Pairing Model

The following result gives the probability of a multigraph from ${\mathcal {P}}_{n,d}$ being simple. It is only valid up to $d=o(n^{1/3})$.

$P({\mathcal {P}}_{n,d}{\hbox{ is simple}})\sim \exp(-d^{2}/4)$.

Since the expected time of generating a simple graph is exponential to d^2, the algorithm will get slow when d gets large.

References

• .
• Béla Bollobás, Random Graphs, 2nd edition, Cambridge University Press, 2001 (sections 2.4, 7.6, 10.3).
• N.C.Wormald, Models of random regular graphs, In Surveys in Combinatorics, pages 239-298. Cambridge University Press, 1999.

≥