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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Generating random regular graphs quickly.

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 .

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

CUSU Lounge Average on weekdays: 9139.47692308 kWh The Meade Room (1st floor of the Marshall Library)

Other talks

How Far Can Good Go Without God? The Limits of a Naturalistic Ethic Precision psychiatry LCLU Annual Talk: The Early Aqueous Environment of Mars Inferred From Mission Lifetime Results by the Curiosity Rover at Gale Crater Title TBC Morning Break / Group Photo Talk title TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity