A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
复制标题
DOI：
10.1109/focs52979.2021.00024
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Dorna Abdolazimi;Kuikui Liu;S. Gharan
中科院分区：
文献类型：
--
作者：
Dorna Abdolazimi;Kuikui Liu;S. Gharan
我们证明了自然的Glauber动力学混合迅速，并且当颜色数至少为$q\geq时，生成最大度为$\Delta$的图的随机真边染色（\frac{10}{3}+\Delta）\Delta$，其中$\Delta> 0$是任意的，并且对于常数$C=C，最大次数满足$\Delta\geq C$（\n）$仅依赖于$\n $，对于边着色，这改进了以前的工作[Vig 99; Che+19]，当$q\geq（\frac{11}{3}-\frac_{0}）\Delta$时，显示快速混合，其中$\frac_{0}\approx 10^{-5}$是一个小的固定常数。在我们的证明的核心，我们建立了一个矩阵涓滴定理，推广了Oppenheim的有影响力的结果，作为一种新的技术来证明，一个高维单纯复形是一个本地频谱扩展。
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $\Delta$ whenever the number of colors is at least $q\geq(\frac{10}{3}+\epsilon)\Delta$, where $\epsilon > 0$ is arbitrary and the maximum degree satisfies $\Delta\geq C$ for a constant $C=C(\epsilon)$ depending only on $\epsilon$, For edge-colorings, this improves upon prior work [Vig99; Che+19] which show rapid mixing when $q\geq(\frac{11}{3}-\epsilon_{0})\Delta$, where $\epsilon_{0}\approx 10^{-5}$ is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheim's influential result, as a new technique to prove that a high dimensional simplicial complex is a local spectral expander.