- 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 graph s 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 frommathcal{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, inmathcal{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 Xi=Xi,n (i>=3) be the number of cycles of length i in agraph in mathcal{G}_{n,d}. For fixed k>=3, X3,...,Xk are asymptotically independent Poisson random variables with meanslambda_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.
Wikimedia Foundation. 2010.