The degree-restricted random process is far from uniform

2022/11/02 by Michael Molloy, Molloy, Michael, Erlang Surya +3 · 1 citation
Computer Science · Mathematics · #05C80 #60C05 #60G99 #68W20 #90B15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2211.00835

openalex publication_date 2022/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d₁, …, d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform random d-regular graph. In this paper we show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. The combinatorial proof technique is our main conceptual contribution: we adapt the switching method to the degree-restricted process, demonstrating that this enumeration technique can also be used to analyze stochastic processes (rather than just uniform random models, as before).

Cited by

• On random bipartite graphs evolving by degrees

Related

• On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
• Local limit of the random degree constrained process
• Behavior of the Minimum Degree Throughout the d-process
• On the uniform generation of random graphs with prescribed degree sequences
• The Degree Sequence of a Scale-Free Random Graph Process with Hard Copying