Behaviour of the minimum degree throughout the -process

The d -process generates a graph at random by starting with an empty graph with n vertices, then adding edges one at a time uniformly at random among all pairs of vertices which have degrees at most $d-1$ and are not mutually joined. We show that, in the evolution of a random graph with n vertices under the d -process with d fixed, with high probability, for each j ∈ \0,1,,d-2\ , the minimum degree jumps from j to $j+1$ when the number of steps left is on the order of ln (n)ᵈ⁻ʲ⁻¹ . This answers a question of Ruciński and Wormald. More specifically, we show that, when the last vertex of degree j disappears, the number of steps left divided by ln (n)ᵈ⁻ʲ⁻¹ converges in distribution to the exponential random variable of mean j!/2(d-1)! ; furthermore, these $d-1$ distributions are independent.