The phase transition in the random d-process

Combinatorics Seminar
Friday, August 26, 2016 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
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 (starting with an empty graph on n vertices, it 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 (Monash University).