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

Vishesh Jain, Marcus Michelen, Huy Tuan Pham +1

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_{Δ,δ}(k\…