EVENT DETAILS AND ABSTRACT

Title: Optimal mixing of the down-up walk on independent sets of a given size
Speaker: Marcus Michelen
Speaker Info: UIC
Brief Description:
Special Note:
Abstract:

Consider a graph of maximum degree D. If we want to sample an independent set of density alpha, a natural Markov chain is to start with an arbitrary independent set of density alpha, remove an element of it uniformly at random, and add a legal choice to the independent set uniformly at random. This Markov chain is called the "down-up walk." I'll discuss a proof of optimal mixing of this Markov chain provided alpha is less than the NP-hardness threshold for this problem. The proof uses the machinery of spectral independence and crucially uses a zero-free region of a certain generating function. I'll give a birds-eye-view of how these tools are used and describe connections between these techniques and various notions of phase transitions; an emphasis will be given on how these tools can be used and intuition for why they work, rather than the technical details. Based on joint work with Vishesh Jain, Huy Tuan Pham and Thuy-Duong Vuong.