BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Generating random regular graphs quickly.  - Prof Oliver Riordan (
 Oxford)
DTSTART:20230126T143000Z
DTEND:20230126T153000Z
UID:TALK196276@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION: A {\\it random $d$-regular graph} is just a $d$-regular simpl
 e graph on $[n]=\\{1\,2\,\\ldots\,n\\}$ chosen uniformly at random from al
 l such graphs. This model\, with $d=d(n)$\, is one of the most natural ran
 dom graph models\, but is quite tricky to work with/reason about\, since a
 ctually generating such a graph is not so easy. For $d$ constant\, Bollob\
 \'as's configuration model works well\; for larger $d$ one can combine thi
 s 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$. T
 he trick allows us to do this without calculating $N(G)$\, which would tak
 e too long. 
LOCATION:MR12
END:VEVENT
END:VCALENDAR