Repository logo
 

Rapid mixing of hypergraph independent sets

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Sly, Allan 
Zhang, Y 

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

Volume Title

54

Publisher

Wiley
Sponsorship
Financial support by the EPSRC grant EP/L018896/1 (J.H.).