Graphs and Matroids Seminar - Jane Gao

Title: Uniformly generate graphs with given degrees rapidly

Abstract:

I will survey the research on exact/approximate uniform generation of graphs with prescribed degrees. In the case that the degrees are not too large (smaller than $n^{1/3}$ where $n$ is the number of vertices), the fastest uniform sampler in the past can generate a graph using $O(\Delta^4 n^2)$ time, where $\Delta$ is the maximum degree. The sampler is based on the switching method, and this time complexity was thought to be the best possible using this method. In this talk I will explain a trick to improve the algorithm to linear time. The talk is based on joint work with Andrii Arman and Nick Wormald.