Richard P. Stanley Seminar in Combinatorics: Optimal mixing of the down-up walk on fixed-size independent sets

Markov chains provide a natural approach to sample from various distributions on the independent sets of a graph. For the uniform distribution on independent sets of a given size $k$ in a graph, perhaps the most natural Markov chain is the so-called “down-up walk”. The down-up walk, which essentially goes back to the foundational work of Metropolis, Rosenbluth, Rosenbluth, Teller and Teller on the Markov Chain Monte Carlo method, starts at an arbitrary independent set of size $k$, and in every step, removes an element uniformly at random and adds a uniformly random legal choice.

Davies and Perkins showed that there is a critical $k = \alpha(\Delta)n$ such that it is hard to (approximately) sample from the uniform distribution on independent sets for the class of graphs $G$ with $n$ vertices and maximum degree at most $\Delta$. They conjectured that for $k$ below this critical value, the down-up walk mixes in polynomial time. I will discuss a resolution of this conjecture, which additionally shows that the down-up walk mixes in (optimal) time $O_{\Delta}(n\log{n})$.

Based on joint work with Marcus Michelen, Huy Tuan Pham, and Thuy-Duong Vuong.

===============================

For more info, see https://math.mit.edu/combin/