Talks
Fall 2022

The Degree-Restricted Random Process Is Far From Uniform

Wednesday, September 28th, 2022, 9:00 am9:45 am

Add to Calendar

Speaker: 

Lutz Warnke (UC San Diego)

Location: 

Calvin Lab Auditorium

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.

AttachmentSize
PDF icon simonstalkwebpage.pdf460.68 KB