Eigenvalue inequalities for graphs and convex subgraphs

Fan RK Chung Shing-Tung Yau

Convex and Discrete Geometry mathscidoc:1912.43552

Communications in Analysis and Geometry, 5, (4), 575-623, 1997
As> iVinf^ b^ where dx denotes the degree of the vertex x. In particular, we derive lower bounds of eigenvalues for convex subgraphs which consist of lattice points in an d-dimensional Riemannian manifolds M with convex boundary. The techniques involve both the (discrete) heat kernels of graphs and improved estimates of the (continuous) heat kernels of Riemannian manifolds. We prove eigenvalue lower bounds for convex subgraphs of the form ce2/(dD (M)) 2 where e denotes the distance between two closest lattice points, D (M) denotes the diameter of the manifold M and c is a constant (independent of the dimension d and the number of vertices in 5, but depending on the how" dense" the lattice points are). This eigenvalue bound is useful for bounding the rates of convergence for various random walk problems. Since many enumeration problems can be approximated by considering random walks in convex subgraphs of some appropriate host graph, the eigenvalue inequalities here have many applications.
No keywords uploaded!
[ Download ] [ 2019-12-24 20:40:14 uploaded by yaust ] [ 368 downloads ] [ 0 comments ]
  title={Eigenvalue inequalities for graphs and convex subgraphs},
  author={Fan RK Chung, and Shing-Tung Yau},
  booktitle={Communications in Analysis and Geometry},
Fan RK Chung, and Shing-Tung Yau. Eigenvalue inequalities for graphs and convex subgraphs. 1997. Vol. 5. In Communications in Analysis and Geometry. pp.575-623. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191224204014450848116.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved