Evolution of random graph processes with degree constraints

This manuscript provides the results presented in my talk at the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, dedicated to Jaroslav Nešetřil on the occasion of his 60th birthday, Prague, July 10-15, 2006.A random graph process is a Markov chain whose state space is the set of all labeled graphs on n vertices. It starts with n isolated vertices, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. A seminal example is the standard random graph process introduced by Erdős and Rényi. We study random graph processes with degree constraints, which recently attracted much attention. In particular we investigate how a graph generated by such a process evolves as the number of edges increases and discuss when the unique largest component first appears, how big the largest component is, and how the probability of a graph being connected changes.