Rapid mixing of hypergraph independent sets
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
We prove that the mixing time of the Glauber dynamics for sampling independent sets on n-vertex k-uniform hypergraphs is 0(n log n) when the maximum degree Δ satisfies Δ ≤ c2k/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·2k/2.
Description
Keywords
approximate counting, hypergraph independent sets, mixing time
Journal Title
Random Structures and Algorithms
Conference Name
Journal ISSN
1042-9832
1098-2418
1098-2418
Volume Title
54
Publisher
Wiley
Publisher DOI
Sponsorship
Financial support by the EPSRC grant EP/L018896/1 (J.H.).