Rapid mixing of hypergraph independent sets. Issue 4 (28th November 2018)

• Record Type: Journal Article
• Authors: Hermon, Jonathan; Sly, Allan; Zhang, Yumeng
• Is Part Of: Random structures & algorithms. Volume 54:Issue 4(2019)
• Page Start: 730
• Page End: 767
• Publication Date: 2018-11-28
• Subjects: approximate counting -- hypergraph independent sets -- mixing time; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20830
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .