# Generating random regular graphs quickly.

• Prof Oliver Riordan (Oxford)
• Thursday 26 January 2023, 14:30-15:30
• MR12.

A {\it random $d$-regular graph} is just a $d$-regular simple graph on $[n]=\{1,2,\ldots,n\}$ chosen uniformly at random from all such graphs. This model, with $d=d(n)$, is one of the most natural random graph models, but is quite tricky to work with/reason about, since actually generating such a graph is not so easy. For $d$ constant, Bollob\’as’s configuration model works well; for larger $d$ one can combine this with switching arguments pioneered by McKay and Wormald. I will discuss recent progress with Nick Wormald, pushing linear-time generation up to $d=o(\sqrt{n})$. One ingredient is {\it reciprocal rejection sampling}, a trick for `accepting’ a certain graph with a probability proportional to $1/N(G)$, where $N(G)$ is the number of certain configurations in $G$. The trick allows us to do this without calculating $N(G)$, which would take too long.

This talk is part of the Combinatorics Seminar series.