论文标题
Cheeger不平等的顶点扩展和重新持续特征值
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
论文作者
论文摘要
经典的Cheeger的不平等将图的边缘电导$ ϕ $与Laplacian矩阵的第二小特征值$λ_2$相关联。最近，Olesker-Taylor和Zanetti发现了一个Cheeger型不平等$ψ^2 / \ log | V | \lysSimλ_2^* \ lyssimψ$连接agragh $ g =（v，e）$的顶点膨胀$ψ$和Laplacian Matrix的最大重新重量第二小eigenvalue $λ_2^* $。 在这项工作中，我们首先将其结果提高到$ψ^2 / \ log d \sillesimλ_2^* \ sillesimψ$，其中$ d $是$ g $中的最高度，这是最佳的，假设小型扩展猜想是最佳的。此外，改进的结果可用于加权顶点的扩展，回答了Olesker-Taylor和Zanetti的一个悬而未决的问题。然后，在这一联系的基础上，我们开发了一种新的光谱理论来扩展顶点。我们发现，与边缘电导和特征值有关的几种有趣的概括在将顶点扩展和重新持续特征值关联时具有近距离的类似物。其中包括对特雷维斯（Trevisan）的结果的类似物，对高级Cheeger不平等的类似物以及改善Cheeger不平等的类似物。 最后，受此连接的启发，我们向Mihail和Vazirani的$ 0/1 $ - Polytope Edge Edge Expention猜想提供了负面证据。我们构建了$ 0/1 $ - polytopes，其图形的顶点扩展非常差。这意味着，在这些$ 0/1 $ - polytopes的顶点上最快的混合时间几乎是线性的。这并不能为猜想提供反例，但这与已知的阳性结果相反，该结果证明了$ 0/1 $ - 聚topopes的子类顶点上的均匀分布。
The classical Cheeger's inequality relates the edge conductance $ϕ$ of a graph and the second smallest eigenvalue $λ_2$ of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality $ψ^2 / \log |V| \lesssim λ_2^* \lesssim ψ$ connecting the vertex expansion $ψ$ of a graph $G=(V,E)$ and the maximum reweighted second smallest eigenvalue $λ_2^*$ of the Laplacian matrix. In this work, we first improve their result to $ψ^2 / \log d \lesssim λ_2^* \lesssim ψ$ where $d$ is the maximum degree in $G$, which is optimal assuming the small-set expansion conjecture. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include an analog of Trevisan's result on bipartiteness, an analog of higher order Cheeger's inequality, and an analog of improved Cheeger's inequality. Finally, inspired by this connection, we present negative evidence to the $0/1$-polytope edge expansion conjecture by Mihail and Vazirani. We construct $0/1$-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these $0/1$-polytopes is almost linear in the graph size. This does not provide a counterexample to the conjecture, but this is in contrast with known positive results which proved poly-logarithmic mixing time to the uniform distribution on the vertices of subclasses of $0/1$-polytopes.
