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,\cdots ,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}$\sim \exp \left({\frac {1-d^{2}}{4}}\right)$.

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\geq 3)\$$ be the number of cycles of length i in a graph in $\${\mathcal {G}}_{n,d}\$$. For fixed $\$k\geq 3\$,\$X_{3},...,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.