A Perfect Sampler for Hypergraph Independent Sets

2022/05/04 by Guoliang Qiu, Qiu, Guoliang, Yanheng Wang +3 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2205.02050

openalex publication_date 2022/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a condition similar to that of the asymmetric Lovász Local Lemma. When applied to d-regular k-uniform hypergraphs on n vertices, our sampler terminates in expected O(nlog n) time provided d≤ c⋅ 2^k/2/k for some constant c>0. If in addition the hypergraph is linear, the condition can be weaken to d≤ c⋅ 2^k/k² for some constant c>0, matching the rapid mixing condition for Glauber dynamics in Hermon, Sly and Zhang [HSZ19].

Cited by

• Tight Bounds for Sampling q-Colorings via Coupling from the Past

Related

• Independent Sets in Hypergraphs
• Inapproximability of Counting Independent Sets in Linear Hypergraphs
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• A Simple Regularization of Hypergraphs
• Hypergraph regularity and random sampling