论文标题
高维扩张器和对铁杆模型的应用中的光谱独立性
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
论文作者
论文摘要
我们说，如果关联的关联矩阵具有最大的特征值，则概率分布$μ$在频谱上是独立的，用于分布及其所有条件分布。我们证明，如果$μ$在频谱上是独立的，那么相应的高维基络合物是局部光谱扩展器。利用最近在简单复合物上混合高维时间的一系列作品\ cite \ cite {km17，dk17，ko18，al19}，这意味着相应的glauber动力学会迅速混合并产生（近似于$μ$的）样品（大致）。 作为一种应用，我们表明天然的Glauber动力学会迅速混合（在多项式时间），从而生成从硬核模型到唯一性阈值的随机独立集。这改善了Weitz确定性相关性衰减算法的准分子运行时间\ cite {WEI06}用于估计硬核分区功能，还回答了混合Glauber Dynamics \ cite Dynamics \ cite {lv97，lv99，lv99，lv99，lv99，dg00，dg00，vig01，ehsvy的长期开放问题。
We say a probability distribution $μ$ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if $μ$ is spectrally independent, then the corresponding high dimensional simplicial complex is a local spectral expander. Using a line of recent works on mixing time of high dimensional walks on simplicial complexes \cite{KM17,DK17,KO18,AL19}, this implies that the corresponding Glauber dynamics mixes rapidly and generates (approximate) samples from $μ$. As an application, we show that natural Glauber dynamics mixes rapidly (in polynomial time) to generate a random independent set from the hardcore model up to the uniqueness threshold. This improves the quasi-polynomial running time of Weitz's deterministic correlation decay algorithm \cite{Wei06} for estimating the hardcore partition function, also answering a long-standing open problem of mixing time of Glauber dynamics \cite{LV97,LV99,DG00,Vig01,EHSVY16}.
