Irregular $\mathbf{d_n}$-Process is distinguishable from Uniform Random $\mathbf{d_n}$-graph

Graph Theory Seminar
Tuesday, November 16, 2021 - 3:45pm for 1 hour (actually 50 minutes)
Skiles 005
Erlang Surya – Georgia Institute of Technology – esurya3@gatech.edu
Anton Bernshteyn

For a graphic degree sequence $\mathbf{d_n}= (d_1 , . . . , d_n)$ of graphs with vertices $v_1 , . . . , v_n$, $\mathbf{d_n}$-process is the random graph process that inserts one edge at a time at random with the restriction that the degree of $v_i$ is at most $d_i$ . In 1999, N. Wormald asked whether the final graph of random $\mathbf{d_n}$-process is "similar" to the uniform random graph with degree sequence $\mathbf{d_n}$ when $\mathbf{d_n}=(d,\dots, d)$. We answer this question for the $\mathbf{d_n}$-process when the degree sequence $\mathbf{d_n}$ that is not close to being regular. We used the method of switching for stochastic processes; this allows us to track the edge statistics of the $\mathbf{d_n}$-process. Joint work with Mike Molloy and Lutz Warnke.