COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Generating random regular graphs quickly.Add to your list(s) Download to your calendar using vCal - Prof Oliver Riordan (Oxford)
- Thursday 26 January 2023, 14:30-15:30
- MR12.
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. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- Combinatorics Seminar
- DPMMS Lists
- DPMMS Pure Maths Seminar
- DPMMS info aggregator
- DPMMS lists
- Hanchen DaDaDash
- Interested Talks
- MR12
- School of Physical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsইন্টারনেট মানেই বিশ্বাসযোগ্য নয় Changing Health Type the title of a new list here## Other talksResearch in the Goldman group: pandemic-scale phylogenetics, and optimizing new sequencing technologies Keeping up the pressure Deformations of symmetric product orbifolds Meta-monuments: storytelling, collaboration and the proxy-wars of public art Outcome and Complications Associated with Cholecystoenterostomy Surgery in Dogs and Cats Planning and Economic Studies Section of the IAEA |