General Cheeger inequalities for p-Laplacians on graphs

DOI10.1016/J.NA.2016.07.011zbMATH Open1348.05126arXiv1509.06062OpenAlexW2208868094MaRDI QIDQ334094FDOQ334094

Matthias Keller, Delio Mugnolo

Publication date: 31 October 2016

Published in: Nonlinear Analysis. Theory, Methods \& Applications. Series A: Theory and Methods (Search for Journal in Brave)

Abstract: We prove Cheeger inequalities for p-Laplacians on finite and infinite weighted graphs. Unlike in previous works, we do not impose boundedness of the vertex degree, nor do we restrict ourselves to the normalized Laplacian and, more generally, we do not impose any boundedness assumption on the geometry. This is achieved by a novel definition of the measure of the boundary which is using the idea of intrinsic metrics. For the non-normalized case, our bounds on the spectral gap of p-Laplacians are already significantly better for finite graphs and for infinite graphs they yield non-trivial bounds even in the case of unbounded vertex degree. We, furthermore, give upper bounds by the Cheeger constant and by the exponential volume growth of distance balls.

Full work available at URL: https://arxiv.org/abs/1509.06062

Recommendations

• Cheeger inequalities for unbounded graph Laplacians
• Cheeger inequality for infinite graphs
• The spectrum of the \(p\)-Laplacian and \(p\)-harmonic morphisms on graphs
• On the Cheeger-Buser type inequalities for the \(p\)-Laplacian
• A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian

zbMATH Keywords

Cheeger inequalitiesintrinsic metrics for Dirichlet formsspectral theory of graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis on local Dirichlet spaces. I. Recurrence, conservativeness and Lp-Liouville properties.
• Isoperimetric estimates for the first eigenvalue of the \(p\)-Laplace operator and the Cheeger constant.
• Title not available (Why is that?)
• Spectral clustering and biclustering. Learning large graphs and contingency tables
• Isoperimetric constants and the first eigenvalue of a compact riemannian manifold
• Title not available (Why is that?)
• Complete manifolds with positive spectrum
• Intrinsic metrics for non-local symmetric Dirichlet forms and applications to spectral theory
• A note on self-adjoint extensions of the Laplacian on weighted graphs
• Unbounded Laplacians on Graphs: Basic Spectral Properties and the Heat Equation
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Intrinsic Metrics on Graphs: A Survey
• Gaussian upper bounds for heat kernels of continuous time simple random walks
• Title not available (Why is that?)
• Lower Bounds for the Partitioning of Graphs
• Pointwise estimates and quasilinear parabolic equations
• Isoperimetric inequalities, growth, and the spectrum of graphs
• A relation between growth and the spectrum of the Laplacian
• Generalized extremal length of an infinite network
• \(p\)-harmonic functions on graphs and manifolds
• The spectrum of the \(p\)-Laplacian and \(p\)-harmonic morphisms on graphs
• Growth and the spectrum of the Laplacian of an infinite graph
• Cheeger inequalities for unbounded graph Laplacians
• Volume growth and bounds for the essential spectrum for Dirichlet forms
• Discrete Calculus
• Title not available (Why is that?)
• Parabolic theory of the discrete \(p\)-Laplace operator
• On the First Eigenvalue of the Combinatorial Laplacian for a Graph.
• On stochastic completeness of jump processes
• Title not available (Why is that?)
• Time regularity and long-time behavior of parabolic \(p\)-Laplace equations on infinite graphs
• Title not available (Why is that?)

Cited In (25)

• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• Generalizations of Szőkefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory
• Parabolicity and Cheeger's constant on graphs
• Cheeger inequality for infinite graphs
• Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
• The pth Kazdan–Warner equation on graphs
• The Kazdan-Warner equation on canonically compactifiable graphs
• Gagliardo-Nirenberg-Sobolev inequalities on planar graphs
• The 1-Yamabe equation on graphs
• The limit of first eigenfunctions of the \(p\)-Laplacian on graphs
• Strong Isoperimetric Inequality for Tessellating Quantum Graphs
• A Cheeger Inequality for the Graph Connection Laplacian
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• Torsional Rigidity in Random Walk Spaces
• Persistent Laplacians: Properties, Algorithms and Implications
• Kazdan-Warner equation on infinite graphs
• On the \(p\)-torsional rigidity of combinatorial graphs
• Sobolev spaces on locally finite graphs
• Asymptotic estimates for the \(p\)-Laplacian on infinite graphs with decaying initial data
• The spectrum of the \(p\)-Laplacian and \(p\)-harmonic morphisms on graphs
• On Cheeger-type inequalities for weighted graphs
• Geometric and spectral properties of directed graphs under a lower Ricci curvature bound
• Spectral estimates for infinite quantum graphs
• Magnetic-sparseness and Schrödinger operators on graphs

This page was built for publication: General Cheeger inequalities for \(p\)-Laplacians on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334094)