Sharper analysis of the random graph d-process via a balls-in-bins model
Abstract
A random 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 of vertices which are not yet edges and have current degrees less than d. If, in the final graph, at most one vertex has degree d−1 and all others 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 nonsaturation of the process.
Fields of Study & Subjects
Stochastic processes and statistical mechanics
Bayesian Methods and Mixture Models
Probability and Risk Models
Publication details
- Journal / source
- The Annals of Applied Probability
- Volume
- 36
- Issue
- 3
- Publication date
- 1 June 2026
- Language
- EN