Curvature and higher order Buser inequalities for the graph connection Laplacian

Liu, Shiping; Muench, Florentin; Peyerimhoff, Norbert

Abstract

We study the eigenvalues of the connection Laplacian on a graph with an orthogonal group or unitary group signature. We establish higher order Buser type inequalities, i.e., we provide upper bounds for eigenvalues in terms of Cheeger constants in the case of nonnegative Ricci curvature. In this process, we discuss the concepts of Cheeger type constants and a discrete Ricci curvature for connection Laplacians and study their properties systematically. The Cheeger constants are defined as mixtures of the expansion rate of the underlying graph and the frustration index of the signature. The discrete curvature, which can be computed efficiently via solving semidefinite programming problems, has a characterization by the heat semigroup for functions combined with a heat semigroup for vector fields on the graph.

Citation

Liu, S., Muench, F., & Peyerimhoff, N. (2019). Curvature and higher order Buser inequalities for the graph connection Laplacian. SIAM Journal on Discrete Mathematics, 33(1), 257-305. https://doi.org/10.1137/16m1056353

• Journal Article Type: Article
• Acceptance Date: Dec 17, 2019
• Online Publication Date: Feb 5, 2019
• Publication Date: Feb 28, 2019
• Deposit Date: Jan 22, 2019
• Publicly Available Date: Apr 11, 2019
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 33
• Issue: 1
• Pages: 257-305
• DOI: https://doi.org/10.1137/16m1056353
• Public URL: https://durham-repository.worktribe.com/output/1309724