Random regular graph

From Wikipedia, the free encyclopedia

You have new messages (last change).
This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

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.

Contents

[edit] 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.

[edit] 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(n1 / 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.

[edit] 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 a graph in \mathcal{G}_{n,d}. For fixed k>=3, X3,...,Xk are asymptotically independent Poisson random variables with means \lambda_i=\frac{(d-1)^i}{2i}.

[edit] References

  • N.C.Wormald, Models of random regular graphs, In Surveys in Combinatorics, pages 239-298. Cambridge University Press, 1999.
This article or section does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any material not supported by sources may be challenged and removed at any time. This article has been tagged since March 2007.
Retrieved from "http://en.wikipedia.org../../../r/a/n/Random_regular_graph.html"