The Degree-Restricted Random Process Is Far From Uniform
5Lutz Warnke (UC San Diego)
https://simons.berkeley.edu/node/22601
Graph Limits, Nonparametric Models, and Estimation
The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1,...,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.
It is natural to ask whether the final graph of this process is similar to a uniform random graph with degree sequence D_n (for d-regular degree sequences D_n this was already raised by Wormald in the mid 1990s).
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.
Our proof uses the switching method, which is usually only applied to uniform random graph models -- rather than to stochastic processes.
Based on joint work with Mike Molloy and Erlang Surya.