##### Department of Mathematics,

University of California San Diego

****************************

### Combinatorics Seminar

## Lutz Warnke

#### UCSD

## The degree-restricted random process is far from uniform

##### Abstract:

The random d-process corresponds to a natural algorithmic model for generating d-regular graphs: starting with an empty graph on n vertices, it evolves by sequentially adding new random edges so that the maximum degree remains at most d.

In 1999 Wormald conjectured that the final graph of the random d-process is "similar" to a uniform random d-regular graph.

We show that this conjecture does not extend to a natural generalization of this process with mixed degree restrictions, i.e., where each vertex has its own degree restriction (under some mild technical assumptions).

Our proof uses the method of switchings, which is usually only applied to uniform random graph models -- rather than to stochastic processes.

Based on joint work in progress with Mike Molloy and Erlang Surya.

### May 31, 2022

### 4:00 PM

AP&M 7218

****************************