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.
Original language | English (US) |
---|---|
Pages (from-to) | 730-767 |
Number of pages | 38 |
Journal | Random Structures and Algorithms |
Volume | 54 |
Issue number | 4 |
DOIs | |
State | Published - Jul 2019 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Keywords
- approximate counting
- hypergraph independent sets
- mixing time