Feb. 9, 3:30pm, Wean 8220

Lutz Warnke, Georgia Tech

The phase transition in the random*d*-process

Lutz Warnke, Georgia Tech

The phase transition in the random

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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.