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

Let G be a graph on n vertices of maximum degree ∆. We show that, for any δ > 0, the down-up walk on independent sets of size k ≤ (1 -δ)αc(∆)n mixes in time O ∆,δ (k log n), thereby resolving a conjecture of Davies and Perkins in an optimal form. Here, αc(∆)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 ∆. 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 = Ω ∆ (n) in this range, we establish a log-Sobolev inequality with optimal constant Ω ∆,δ (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 ℓ∞-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.

2 see Section 3 for an interpretation of this function. Here, we only note that αc(∆) = (1+o ∆ (1))e (1+e)∆ . 3 Recall that the ε-mixing time of a Markov chain with transition matrix P and stationary distribution µ on state space Ω is defined to be τ mix (ε) = maxν mint ≥ 0 : TV(νP t , µ) ≤ ε, where TV denotes the total variation distance between probability distributions and the max ranges over all probability distributions ν on Ω.