On 06.12.2016 at 14:00 in S1, there is the following noon lecture:
The phase transition in the random d-process
University of Cambridge and Georgia Institute of Technology
(based on joint work with Nick Wormald)
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 Balińska and Quintas from 1990.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010