- Series
- Combinatorics Seminar
- Time
- Friday, January 24, 2020 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Andrii Arman – Emory University – andrii.arman@emory.edu – https://sites.google.com/view/a-arman/home
- Organizer
- Lutz Warnke
In this talk I will discuss algorithms for a uniform generation of random graphs with a given degree sequence. Let $M$ be the sum of all degrees and $\Delta$ be the maximum degree of a given degree sequence. McKay and Wormald described a switching based algorithm for the generation of graphs with given degrees that had expected runtime $O(M^2\Delta^2)$, under the assumption $\Delta^4=O(M)$. I will present a modification of the McKay-Wormald algorithm that incorporates a new rejection scheme and uses the same switching operation. A new algorithm has expected running time linear in $M$, under the same assumptions.
I will also describe how a new rejection scheme can be integrated into other graph generation algorithms to significantly reduce expected runtime, as well as how it can be used to generate contingency tables with given marginals uniformly at random.
This talk is based on the joint work with Jane Gao and Nick Wormald.