Markov chains on fixed-size independent sets: Optimal mixing from spectral independence, local CLT, and log-Sobolev inequality

Mon November 27th 2023, 4:00pm
Sequoia 200
Huy Pham, Stanford Math

Markov chains give natural approaches to sample from various distributions on independent sets of graphs. Considering the uniform distribution on independent sets of a fixed size k in a graph G, the corresponding Markov chain is the "down-up" walk. The down-up walk 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.

For graphs G on n vertices with bounded maximum degree D, and for k at most a tight critical threshold, I will discuss a proof that the down-up walk mixes in the (optimal) O(n log n) time. The proof combines the spectral independence framework with three new ingredients. First, we obtain precise local CLT-type estimates leveraging zero-free regions of the partition function in the complex plane. Second, we develop a version of the Lee-Yau induction to show log-Sobolev inequalities for distributions on sets of size k with significantly less symmetry than the uniform distribution. Finally, we show a sharp Markov chain decomposition result using a version of Stein’s method for Markov chains.

This talk is based on joint work with Vishesh Jain, Marcus Michelen and Thuy-Duong Vuong.