Behavior of the Minimum Degree Throughout the d-process

2023/08/30 by Jakob Hofstad, Hofstad, Jakob
Mathematics · Physics and Astronomy · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2308.16111

openalex publication_date 2023/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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)^d-j-1. 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)^d-j-1 converges in distribution to the exponential random variable of mean (j!)/(2(d-1)!); furthermore, these d-1 distributions are independent.

Related

• On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
• Minimum degree k and k-connectedness usually arrive together
• The degree-restricted random process is far from uniform
• Sharper analysis of the random graph d-process via a balls-in-bins model
• The Degree Sequence of a Scale-Free Random Graph Process with Hard Copying