Nonlinear Spectral Graph Theory

Abstract

Nonlinear spectral graph theory is an extension of the traditional (linear) spectral graph theory and studies relationships between spectral properties of nonlinear operators defined on a graph and topological properties of the graph itself. Many of these relationships get tighter when going from the linear to the nonlinear case. In this manuscript, we discuss the spectral theory of the graph p-Laplacian operator. In particular we report links between the p-Laplacian spectrum and higher-order Cheeger (or isoperimetric) constants, sphere packing constants, independence and matching numbers of the graph. The main aim of this paper is to present a complete and self-contained introduction to the problem accompanied by a discussion of the main results and the proof of new results that fill some gaps in the theory. The majority of the new results are devoted to the study of the graph infinity Laplacian spectrum and the information that it yields about the packing radii, the independence numbers and the matching number of the graph. This is accompanied by a novel discussion about the nodal domains induced by the infinity eigenfunctions. There are also new results about the variational spectrum of the p-Laplacian, the regularity of the p-Laplacian spectrum varying p, and the relations between the 1-Laplacian spectrum and new Cheeger constants.

Please cite this paper as:

@article{deidda2025nonlinear,
  title={Nonlinear spectral graph theory},
  author={Deidda, Piero and Tudisco, Francesco and Zhang, Dong},
  journal={arxiv:2504.03566},
  year={2025}
}

Keywords: spectral clustering nonlinear eigenvalues graph laplacian graph theory