Volume Growth, Curvature, and Buser-Type Inequalities in Graphs
Volume Growth, Curvature, and Buser-Type Inequalities in Graphs
复制标题
DOI：
10.1093/imrn/rnz305
复制
发表时间：
2018-02
影响因子：
1
通讯作者：
B. Benson;P. Ralli;P. Tetali
中科院分区：
文献类型：
--
作者：
B. Benson;P. Ralli;P. Tetali
我们研究了离散空间中度量球的体积增长作为半径的函数，重点讨论了体积增长与离散曲率之间的关系。我们改进了所谓的Ollivier曲率下界下的体积增长界，并讨论了其他类型的离散Ricci曲率下的类似结果。根据最近(第一作者)在黎曼流形的连续设置下的工作，我们将图的拉普拉斯的特征值限制在体积增长的界下。特别地，图的$\lambda_2$可以用加权离散Hardy不等式来定界，而图的高阶特征值可以由三对角阵的特征值乘以乘法因子来定界，这两者都只依赖于图的体积增长。作为直接应用，我们将本征值与Cheeger等周常数联系起来。利用这些方法，我们描述了在第二个特征值(即第一个非零本征值)上Cheeger不等式紧的图类。我们还描述了一种证明图中的Buser不等式的方法，特别是在曲率的下界假设下。
We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature. Following recent work in the continuous setting of Riemannian manifolds (by the 1st author), we then bound the eigenvalues of the Laplacian of a graph under bounds on the volume growth. In particular, $\lambda _2$ of the graph can be bounded using a weighted discrete Hardy inequality and the higher eigenvalues of the graph can be bounded by the eigenvalues of a tridiagonal matrix times a multiplicative factor, both of which only depend on the volume growth of the graph. As a direct application, we relate the eigenvalues to the Cheeger isoperimetric constant. Using these methods, we describe classes of graphs for which the Cheeger inequality is tight on the 2nd eigenvalue (i.e. the 1st nonzero eigenvalue). We also describe a method for proving Buser’s Inequality in graphs, particularly under a lower bound assumption on curvature.