Random regular graph

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 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((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.