Optimal mixing of the down-up walk on independent sets of a given size

Abstract

Let $G$ be a graph on $n$ vertices of maximum degree $\Delta$. We show that, for any $\delta >0$, the down-up walk on independent sets of size $k\le (1-\delta ){\alpha }_c(\Delta )n$ mixes in time $O_{\Delta ,\delta }(k\log n)$, thereby resolving a conjecture of Davies and Perkins in an optimal form. Here, ${\alpha }_c(\Delta )n$ is the NP-hardness threshold for the problem of counting independent sets of a given size in a graph on $n$ vertices of maximum degree $\Delta$. Our mixing time has optimal dependence on $k,n$ for the entire range of $k$; previously, even polynomial mixing was not known. In fact, for $k={\Omega }_{\Delta }(n)$ in this range, we establish a log-Sobolev inequality with optimal constant ${\Omega }_{\Delta ,\delta }(1/n)$. At the heart of our proof are three new ingredients, which may be of independent interest. The first is a method for lifting ${\ell }_{\infty }$-independence from a suitable distribution on the discrete cube -- in this case, the hard-core model -- to the slice by proving stability of an Edgeworth expansion using a multivariate zero-free region for the base distribution. The second is a generalization of the Lee-Yau induction to prove log-Sobolev inequalities for distributions on the slice with considerably less symmetry than the uniform distribution. The third is a sharp decomposition-type result which provides a lossless comparison between the Dirichlet form of the original Markov chain and that of the so-called projected chain in the presence of a contractive coupling.

25 pages; comments welcome!