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 pairingmodel is described as follows.

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

Let $mathcal\{P\}\_\{n,d\}$ denote the probability space of randomd-regular multigraphs generated by the pairing model asdescribed 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 multigraphfrom $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 isexponential to d^2, the algorithm will get slow when d getslarge.

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