Rapid mixing of hypergraph independent sets

Jonathan Hermon; Allan Sly; Yumeng Zhang

doi:10.1002/rsa.20830

Rapid mixing of hypergraph independent sets

Jonathan Hermon, Allan Sly, Yumeng Zhang

Mathematics

Research output: Contribution to journal › Article › peer-review

23 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 Δ ≤ c2^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.

Original language	English (US)
Pages (from-to)	730-767
Number of pages	38
Journal	Random Structures and Algorithms
Volume	54
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20830
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

Access to Document

10.1002/rsa.20830

Cite this

@article{1ae38be43edc4d31941d671fb3b7c33d,

title = "Rapid mixing of hypergraph independent sets",

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.",

keywords = "approximate counting, hypergraph independent sets, mixing time",

author = "Jonathan Hermon and Allan Sly and Yumeng Zhang",

note = "Publisher Copyright: {\textcopyright} 2018 Wiley Periodicals, Inc.",

year = "2019",

month = jul,

doi = "10.1002/rsa.20830",

language = "English (US)",

volume = "54",

pages = "730--767",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - Rapid mixing of hypergraph independent sets

AU - Hermon, Jonathan

AU - Sly, Allan

AU - Zhang, Yumeng

PY - 2019/7

Y1 - 2019/7

N2 - 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.

AB - 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.

KW - approximate counting

KW - hypergraph independent sets

KW - mixing time

UR - https://www.scopus.com/pages/publications/85057566572

UR - https://www.scopus.com/inward/citedby.url?scp=85057566572&partnerID=8YFLogxK

U2 - 10.1002/rsa.20830

DO - 10.1002/rsa.20830

M3 - Article

AN - SCOPUS:85057566572

SN - 1042-9832

VL - 54

SP - 730

EP - 767

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Rapid mixing of hypergraph independent sets

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this