Sharper analysis of the random graph $d$-process via a balls-in-bins model

Abstract

A graph $d$-process starts with an empty graph on $n$ vertices, and adds one edge at each time step, chosen uniformly at random from those pairs which are not yet edges and whose both vertices have current degree less than $d$. If, in the final graph, at most one vertex has degree $d-1$ and all other have degree $d$, we call the process saturated. We present a new approach to analysing this process based on random allocation of balls in bins. This allows us to get improved results on the degree distribution throughout the process and, consequently, to determine the asymptotic probability of non-saturation of the process.

39 pages