Rapid mixing of hypergraph independent sets. Issue 4 (28th November 2018) - Hermon, Jonathan; Sly, Allan; Zhang, Yumeng
Abstract : We prove that the mixing time of the Glauber dynamics for sampling independent sets on n ‐vertex k ‐uniform hypergraphs is O ( n log n ) when the maximum degree Δ satisfies Δ ≤  c 2 k /2, improving on the previous bound Bordewich and co‐workers of Δ ≤  k  − 2. This result brings the algorithmic bound to within a constant factor of the hardness bound of Bezakova and co‐workers which showed that it is NP‐hard to approximately count independent sets on hypergraphs when Δ ≥ 5·2 k /2 .