Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Prof. Michael Molloy
University of Toronto
The degree-restricted random process is far from uniform
Abstract:
Suppose you wish to generate a random graph on vertices $v_1, ..., v_n$ where the degree of each $v_i$ is specified to be $d_i$. Perhaps the most natural approach is: Repeatedly add an edge joining two vertices chosen uniformly from all non-adjacent pairs that are not yet full (i.e. whose current degrees are less than their specified degrees).
The graph we obtain is not distributed uniformly amongst all graphs with the specified degree sequence (except for some trivial sequences). But is the distribution close to uniform in the sense that every property which holds with high probability in one model holds with high probability in the other?
We answer that question in the negative for bounded degree sequences that are not regular or close to regular.
This is joint work with Erlang Surya and Lutz Warnke; see arXiv:2211.00835
May 21, 2024
2:00 PM
APM 7321
Research Areas
Combinatorics Probability Theory****************************