On the spectrum of hypergraphs

DOI10.1016/J.LAA.2020.01.012MaRDI QIDQ2229474zbMATH OpenOpenAlexWikidataFDO

Authors Anirban Banerjee

Publication date 17 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

Cheeger constantgeneral hypergraphspectral theory of hypergraphsrandom walk on hypergraphsRicci curvature of hypergraphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Positive matrices and their generalizations; cones of matrices (15B48) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Hypergraphs (05C65) Random walks on graphs (05C81) Eigenvalue problems for linear operators (47A75)

Abstract: Here we study the spectral properties of an underlying weighted graph of a non-uniform hypergraph by introducing different connectivity matrices, such as adjacency, Laplacian and normalized Laplacian matrices. We show that different structural properties of a hypergrpah, can be well studied using spectral properties of these matrices. Connectivity of a hypergraph is also investigated by the eigenvalues of these operators. Spectral radii of the same are bounded by the degrees of a hypergraph. The diameter of a hypergraph is also bounded by the eigenvalues of its connectivity matrices. We characterize different properties of a regular hypergraph characterized by the spectrum. Strong (vertex) chromatic number of a hypergraph is bounded by the eigenvalues. Cheeger constant on a hypergraph is defined and we show that it can be bounded by the smallest nontrivial eigenvalues of Laplacian matrix and normalized Laplacian matrix, respectively, of a connected hypergraph. We also show an approach to study random walk on a (non-uniform) hypergraph that can be performed by analyzing the spectrum of transition probability operator which is defined on that hypergraph. Ricci curvature on hypergraphs is introduced in two different ways. We show that if the Laplace operator, $Delta$, on a hypergraph satisfies a curvature-dimension type inequality $CD(mathbfm,mathbfK)$ with $mathbfm>1$ and $mathbfK>0$ then any non-zero eigenvalue of $-Delta$ can be bounded below by $fracmathbfmmathbfKmathbfm-1$. Eigenvalues of a normalized Laplacian operator defined on a connected hypergraph can be bounded by the Ollivier's Ricci curvature of the hypergraph.

Recommendations

• Spectral properties of general hypergraphs
• On some general operators of hypergraphs
• Spectra of general hypergraphs
• Spectra of uniform hypergraphs
• High-ordered random walks and generalized Laplacians on hypergraphs

Cites work

• scientific article; zbMATH DE number 3894218 (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?)
• A characterization of cube-hypergraphs
• A general product of tensors with applications
• A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs
• A sharp upper bound on the spectral radius of weighted graphs
• Bounds on normalized Laplacian eigenvalues of graphs
• Coloring mixed hypergraphs: theory, algorithms and applications
• Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues
• Curvature aspects of graphs
• Diameters and Eigenvalues
• Eigenvalues of a real supersymmetric tensor
• Eigenvalues, diameter, and mean distance in graphs
• Finding the largest eigenvalue of a nonnegative tensor
• Further Results for Perron–Frobenius Theorem for Nonnegative Tensors II
• Further results for Perron-Frobenius theorem for nonnegative tensors
• High-ordered random walks and generalized Laplacians on hypergraphs
• Isoperimetric numbers of graphs
• Laplacian eigenvalues and partition problems in hypergraphs
• Most tensor problems are NP-hard
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• On a conjecture concerning spanning tree invariants and loop systems
• On eigenvalue problems of real symmetric tensors
• On some properties of the determinants of tensors
• On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs
• On the Laplacian Spectrum and Walk-regular Hypergraphs
• On the spectrum of the normalized graph Laplacian
• Perron-Frobenius theorem for nonnegative tensors
• Regular uniform hypergraphs, \(s\)-cycles, \(s\)-paths and their largest Laplacian H-eigenvalues
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Ricci curvature of Markov chains on metric spaces
• Spectra of general hypergraphs
• Spectra of uniform hypergraphs
• Tensor analysis. Spectral theory and special tensors
• The Eigenvalues of a Graph and Its Chromatic Number
• The \(Z\)-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory.
• The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph
• The largest Laplacian and signless Laplacian \(H\)-eigenvalues of a uniform hypergraph
• \(H^{+}\)-eigenvalues of Laplacian and signless Laplacian tensors

Cited in

(30)

• Joins of hypergraphs and their spectra
• Spectra of random regular hypergraphs
• Investigating the connectivity of hypergraphs via their spectra
• Random walks and Laplacians on hypergraphs: when do they match?
• Adjacency energy of hypergraphs
• Cheng's maximal diameter theorem for hypergraphs
• Spectrum of mixed bi-uniform hypergraphs
• Energies of hypergraphs
• On the Laplacian spectrum of \(k\)-uniform hypergraphs
• On the spectrum and number of convex sets in graphs
• Some bounds on spectral radius of signless Laplacian matrix of k-graphs
• Principal eigenvector of the signless Laplacian matrix
• Accessible spectrum of graphs
• Spectral properties of general hypergraphs
• High-ordered random walks and generalized Laplacians on hypergraphs
• Spectra of hyperstars
• Core-Periphery Detection in Hypergraphs
• On Opsut's conjecture for hypercompetition numbers of hypergraphs
• Incidence energy of \(k\)-uniform hypertrees
• Adjacency spectra of random and complete hypergraphs
• A Cheeger cut for uniform hypergraphs
• Spectra of general hypergraphs
• Tensor join of hypergraphs and its spectra
• The stabilizing index and cyclic index of the coalescence and Cartesian product of uniform hypergraphs
• Applying a hypergraph to determine the structure of some finite modules
• High-order random walks and generalized Laplacians on hypergraphs
• Normalized Laplacian eigenvalues of hypergraphs
• On some general operators of hypergraphs
• Functional analysis on hypergraphs: density and zeta functions -- applications to molecular graphs and image analysis
• Spectral extremal results for hypergraphs

This page was built for publication: On the spectrum of hypergraphs

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