University of Cambridge > > Combinatorics Seminar > Generating random regular graphs quickly.

Generating random regular graphs quickly.

Add to your list(s) Download to your calendar using vCal

  • UserProf Oliver Riordan (Oxford)
  • ClockThursday 26 January 2023, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity