On the spectrum of hypergraphs

DOI10.1016/J.LAA.2020.01.012zbMATH Open1459.05158arXiv1711.09356OpenAlexW2999000976WikidataQ126381208 ScholiaQ126381208MaRDI QIDQ2229474FDOQ2229474

Authors: Anirban Banerjee 

Publication date: 17 February 2021

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

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.

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

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

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)

Cites Work

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

Cited In (30)

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