Generating random regular graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n 1/3-ε ) , it is shown that the algorithm generates an asymptotically uniform random d -regular graph on n vertices in time O(nd 2 ) . This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.

Authors

• Jeong Han Kim
• Van H. Vu

Keywords

• concentration
• configuration model
• inequality
• random regular graph