

























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(n\log n)$ time provided $d\le c\cdot 2^{k/2}/k$ for some constant $c>0$. If in addition the hypergraph is linear, the condition can be weaken to $d\le c\cdot 2^{k}/k^2$ for some constant $c>0$, matching the rapid mixing condition for Glauber dynamics in Hermon, Sly and Zhang [HSZ19].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。