Random regular graph

Definition

---

A random d-regular graph is a graph from ${\mathcal {G}}_{n,d}$, which denotes the probability space of all d-regular graphs on vertex set [n], where nd is even and [n]:={1,2,3,...,n-1,n}, with uniform distribution.

Pairing Model

---

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 u.a.r.

Properties of Pairing Model

---

The following result gives the probability of a multigraph from ${\mathcal {P}}_{n,d}$ being simple.

P{${\mathcal {P}}_{n,d}$ is simple}~exp((1-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.

Properties of Random Regular Graphs

---

All local structures but trees and cycles appear in a random regular graph with probability o(1) as n goes to infinity. For any given subset of vertices with bounded size, the subgraph induced by this subset is a tree a.a.s.

The next theorem gives nice property of the distribution of the number of short cycles.
For d fixed, let X_i=X_i,n (i>=3) be the number of cycles of length i in a graph in ${\mathcal {G}}_{n,d}$. For fixed k>=3, X₃,...,X_k are asymptotically independent Poisson random variables with means $\lambda _{i}={\frac {(d-1)^{i}}{2i}}$.

References

---

N.C.Wormald, Models of random regular graphs, In Surveys in Combinatorics, pages 239-298. Cambridge University Press, 1999.