skip to content
 

The phase transition in the random d-process

Presented by: 
Lutz Warnke University of Cambridge, Georgia Institute of Technology
Date: 
Thursday 29th September 2016 - 11:00 to 12:00
Venue: 
INI Seminar Room 2
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.

[ The video of this talk is temporarily unavailable. Please try later. ]

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons