The Degree-Restricted Random Process Is Far From Uniform

          @misc{ scivideos_22601,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22601},
            author = {},
            keywords = {},
            language = {en},
            title = {The Degree-Restricted Random Process Is Far From Uniform},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22601 see, \url{https://scivideos.org/simons-institute/22601}}
          }
          

Abstract

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.