Richard P. Stanley Seminar in Combinatorics: Vishesh Jain (UIC)

Building 2, Room 139

Speaker: Vishesh Jain (University of Illinois Chicago)Title: Optimal mixing of the down-up walk on fixed-sized independents setsAbstract: 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 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 , 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 such that it is hard to (approximately) sample from the uniform distribution on independent sets for the class of graphs with vertices and maximum degree at most . They conjectured that for 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) timeBased on joint work with Marcus Michelen, Huy Tuan Pham, and Thuy-Duong Vuong.