Spectrum of the 1-Laplacian and Cheeger's constant on graphs

DOI10.1002/JGT.21871MaRDI QIDQ3466363zbMATH OpenOpenAlexFDO

Authors Kung Ching Chang

Publication date 1 February 2016

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

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

zbMATH Keywords

1-Laplace operatorCheeger's constantconnected graphLaplace operatorspectral graph theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Spectral theory; eigenvalue problems on manifolds (58C40) Abstract critical point theory (Morse theory, Lyusternik-Shnirel'man theory, etc.) in infinite-dimensional spaces (58E05)

Abstract: We develop a nonlinear spectral graph theory, in which the Laplace operator is replaced by the 1-Laplacian ?$Delt{a}_1$. The eigenvalue problem is to solve a nonlinear system involving a set valued function. In the study, we investigate the structure of the solutions, the minimax characterization of eigenvalues, the multiplicity theorem, etc. The eigenvalues as well as the eigenvectors are computed for several elementary graphs. The graphic feature of eigenvalues are also studied. In particular, Cheeger's constant, which has only some upper and lower bounds in linear spectral theory, equals to the first non-zero ?$$ eigenvalue for connected graphs.

Recommendations

• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
• The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
• A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian
• Nodal domains of eigenvectors for 1-Laplacian on graphs

Cites work

• Deformation properties for continuous functionals and critical point theory
• DIRICHLET PROBLEMS FOR THE 1-LAPLACE OPERATOR, INCLUDING THE EIGENVALUE PROBLEM
• scientific article; zbMATH DE number 3986206 (Why is no real title available?)
• scientific article; zbMATH DE number 2191998 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Isoperimetric estimates for the first eigenvalue of the p-Laplace operator and the Cheeger constant.
• THE SPECTRUM OF THE 1-LAPLACE OPERATOR
• Variational methods for non-differentiable functionals and their applications to partial differential equations

Cited in

(44)

• A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian
• First eigenvalue estimates of Dirichlet-to-Neumann operators on graphs
• Neumann Cheeger constants on graphs
• Eigenvalue bounds for the signless \(p\)-Laplacian
• The limit of first eigenfunctions of the \(p\)-Laplacian on graphs
• Delta invariant for Eulerian digraphs
• Gradient flows in metric random walk spaces
• \(p\)-Laplace operators for oriented hypergraphs
• \((\mathrm{BV},L^p)\)-decomposition, \(p = 1,2\), of functions in metric random walk spaces
• Spectrum of signless 1-Laplacian on simplicial complexes
• The homotopy significant spectrum compared to the Krasnoselskii spectrum
• The existence of extremal functions for discrete Sobolev inequalities on lattice graphs
• The total variation flow in metric random walk spaces
• Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
• Topological multiplicity of the maximum eigenvalue of graph \(1\)-Laplacian
• Positive solutions of Yamabe-type equations with function coefficients on graphs
• The Cheeger cut and Cheeger problem in metric graphs
• Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering
• The 1-Laplacian Cheeger cut: theory and algorithms
• The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
• $H^{1}$-bounds for spectral multipliers on graphs
• Community detection in networks via nonlinear modularity eigenvectors
• Cheeger Constant and Connectivity of Graphs
• Existence of global solutions to some nonlinear equations on locally finite graphs
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• Nodal domains of eigenvectors for 1-Laplacian on graphs
• Data Analytics on Graphs Part I: Graphs and Spectra on Graphs
• The 1-Yamabe equation on graphs
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm
• Nodal domain theorems for p-Laplacians on signed graphs
• The Cheeger cut and Cheeger problem in metric measure spaces
• Invariants for incidence matrix of a tree
• The existence of positive ground state solutions for the Choquard type equation on groups of polynomial growth
• The asymptotic behavior of constant sign and nodal solutions of (p, q)-Laplacian problems as p goes to 1
• Sobolev spaces on locally finite graphs
• The graph -Laplacian eigenvalue problem
• Finding Cheeger cuts via 1-Laplacian of graphs
• The smallest normalized signless -Laplacian eigenvalue for non-bipartite graphs
• Dual Cheeger constants, signless 1-Laplacians and maxcut
• Graph p-Laplacian eigenpairs as saddle points of a family of spectral energy functions
• Homological eigenvalues of graph p-Laplacians
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Nonsmooth critical point theory and applications to the spectral graph theory

This page was built for publication: Spectrum of the 1-Laplacian and Cheeger's constant on graphs

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