论文标题
一个完美的HyperGraph独立套件
A Perfect Sampler for Hypergraph Independent Sets
论文作者
论文摘要
重新审视了均匀采样超图独立集的问题。我们在类似于非对称Lovász局部引理的条件下为问题设计了有效的完美采样器。当应用于$ n $顶点上的$ d $ - 规范$ k $均匀的超图时，我们的采样器将以预期的$ o（n \ log n）$ time终止，提供$ d \ d \ le c \ cdot 2^{k/2}/k $，对于某些常数$ c> 0 $。如果另外，如果超图是线性的，则可以将条件削弱到$ d \ le c \ cdot 2^{k}/k^2 $，对于某些常数$ c> 0 $，与Hermon Sly，Sly和Zhang的Glauber动态的快速混合条件匹配[HSZ19]。
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].
