BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Generating random regular graphs quickly. - Prof
Oliver Riordan (Oxford)
DTSTART;TZID=Europe/London:20230126T143000
DTEND;TZID=Europe/London:20230126T153000
UID:TALK196276AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/196276
DESCRIPTION: A {\\it random $d$-regular graph} is just a $d$-r
egular 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 n
atural random graph models\, but is quite tricky t
o work with/reason about\, since actually generati
ng such a graph is not so easy. For $d$ constant\,
Bollob\\'as's configuration model works well\; fo
r larger $d$ one can combine this with switching a
rguments pioneered by McKay and Wormald. I will di
scuss 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 calculatin
g $N(G)$\, which would take too long.
LOCATION:MR12
CONTACT:
END:VEVENT
END:VCALENDAR