Rapid mixing of hypergraph independent sets

Jonathan Hermon, Allan Sly, Yumeng Zhang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish (US)
Pages (from-to)730-767
Number of pages38
JournalRandom Structures and Algorithms
Volume54
Issue number4
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Rapid mixing of hypergraph independent sets'. Together they form a unique fingerprint.

Cite this