A nodal domain theorem and a higher-order Cheeger inequality for the graph p-Laplacian

DOI10.4171/JST/216MaRDI QIDQ1668115zbMATH OpenFDO

Authors Francesco Tudisco, Matthias Hein

Publication date 31 August 2018

Published in Journal of Spectral Theory (Search for Journal in Brave)

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

zbMATH Keywords

Cheeger inequalitygraph \(p\)-Laplaciangraph clusteringnodal domainsvariational eigenvalues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Discrete version of topics in analysis (39A12) Particular nonlinear operators (superposition, Hammerstein, Nemytski?, Uryson, etc.) (47H30)

Abstract: We consider the nonlinear graph $p$-Laplacian and its set of eigenvalues and associated eigenfunctions of this operator defined by a variational principle. We prove a nodal domain theorem for the graph $p$-Laplacian for any $pgeq1$. While for $p>1$ the bounds on the number of weak and strong nodal domains are the same as for the linear graph Laplacian ($p=2$), the behavior changes for $p=1$. We show that the bounds are tight for $pgeq1$ as the bounds are attained by the eigenfunctions of the graph $p$-Laplacian on two graphs. Finally, using the properties of the nodal domains, we prove a higher-order Cheeger inequality for the graph $p$-Laplacian for $p>1$. If the eigenfunction associated to the $k$-th variational eigenvalue of the graph $p$-Laplacian has exactly $k$ strong nodal domains, then the higher order Cheeger inequality becomes tight as $pightarrow1$.

Review text

Summary: We consider the nonlinear graph \(p\)-Laplacian and its set of eigenvalues and associated eigenfunctions of this operator defined by a variational principle. We prove a nodal domain theorem for the graph \(p\)-Laplacian for any \(p\geq1\). While for \(p>1\) the bounds on the number of weak and strong nodal domains are the same as for the linear graph Laplacian \((p=2)\), the behavior changes for \(p=1\). We show that the bounds are tight for \(p\geq1\) as the bounds are attained by the eigenfunctions of the graph \(p\)-Laplacian on two graphs. Finally, using the properties of the nodal domains, we prove a higher-order Cheeger inequality for the graph \(p\)-Laplacian for \(p>1\). If the eigenfunction associated to the \(k\)-th variational eigenvalue of the graph \(p\)-Laplacian has exactly \(k\) strong nodal domains, then the higher order Cheeger inequality becomes tight as \(p\to1\).

Recommendations

• General Cheeger inequalities for p-Laplacians on graphs
• Spectrum of the 1-Laplacian and Cheeger's constant on graphs
• The limit of first eigenfunctions of the \(p\)-Laplacian on graphs
• Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
• A nodal domain property for the p-Laplacian

Cited in

(22)

• The limit of first eigenfunctions of the \(p\)-Laplacian on graphs
• Multiway \(p\)-spectral graph cuts on Grassmann manifolds
• \(p\)-Laplace operators for oriented hypergraphs
• Partial differential equations and variational methods for geometric processing of images
• Geometric and spectral properties of directed graphs under a lower Ricci curvature bound
• Nonconvex weak sharp minima on Riemannian manifolds
• Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
• Nodal domain count for the generalized graph \(p\)-Laplacian
• Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering
• General Cheeger inequalities for p-Laplacians on graphs
• Spectrum of the 1-Laplacian and Cheeger's constant on graphs
• Community detection in networks via nonlinear modularity eigenvectors
• A Nonlinear Spectral Method for Core--Periphery Detection in Networks
• Total variation based community detection using a nonlinear optimization approach
• Symmetric matrices, signed graphs, and nodal domain theorems
• Nodal domain theorems for p-Laplacians on signed graphs
• Quantifying the structural stability of simplicial homology
• Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
• Sobolev spaces on locally finite graphs
• The graph -Laplacian eigenvalue problem
• Graph p-Laplacian eigenpairs as saddle points of a family of spectral energy functions
• Homological eigenvalues of graph p-Laplacians

This page was built for publication: A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian

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