The phase transition in the random d-process

Speaker(s) Lutz Warnke University of Cambridge; Georgia Institute of Technology
Date 29 September 2016 – 11:00 to 12:00
Venue INI Seminar Room 2
Session Title The phase transition in the random d-process
Event [SNA] Theoretical foundations for statistical network analysis
Abstract One of the most interesting features of Erdös-Rényi random graphs is the `percolation phase transition', where the global structure intuitively changes from only small components to a single giant component plus small ones. In this talk we discuss the percolation phase transition in the random d-process, which corresponds to a natural algorithmic model for generating random regular graphs that differs from the usual configuration model (starting with an empty graph on n vertices, the random d-process evolves by sequentially adding new random edges so that the maximum degree remains at most d). Our results on the phase transition solve a problem of Wormald from 1997, and verify a conjecture of Balinska and Quintas from 1990.   Based on joint work with Nick Wormald.

Supported By