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

Date
Mon November 27th 2023, 4:00pm
Location
Sequoia 200
Speaker
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.