Generating random regular graphs (Q5899329)

Fix a pair of positive integers \(1\leq d<n\) and let \(S(n,d)\) be the set of all simple \(d\)-regular graphs on a set of \(n\) vertices. The uniform random \(d\)-regular graph \(G_{n,d}\) is obtained by sampling with respect to the uniform distribution from \(S(n,d)\). The probability of each simple \(d\)-regular graph is thus \(1/| S(n,d)|\). Since \(nd\) is twice the number of edges in \(G_{n,d}\), we always assume that \(nd\) is even. Despite an extensive study, a very fundamental, and perhaps practically the most important, question concerning random regular graphs has not yet been answered in a satisfactory way: Question: How do we generate a uniform random regular graph? The paper under review presents a contribution to the answer of this question. The authors analyze an algorithm introduced by \textit{A. Steger} and \textit{N. Wormald} [Comb. Probab. Comput. 8, 377--396 (1999; Zbl 0935.05082)] and prove that it produces an asymptotically uniform random \(d\)-regular graph in time \(O(nd^2)\) for \(d\) and \(n\) satisfying \(d=O(n^{1/3-\epsilon})\) as \(n\to\infty\), where \(\epsilon\) is a positive constant. This confirms a conjecture of \textit{N. Wormald} [Lond. Math. Soc. Lect. Note Ser. 267, 239--298 (1999; Zbl 0935.05080)]. The method of proof is based on a recently developed concentration inequality which can be applied to functions with large Lipschitz coefficients.