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 hypergraphrandom walk on hypergraphsRicci curvature of hypergraphsspectral theory of hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Random walks on graphs (05C81) Eigenvalues, singular values, and eigenvectors (15A18) Positive matrices and their generalizations; cones of matrices (15B48) 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

• \(H^{+}\)-eigenvalues of Laplacian and signless Laplacian tensors
• 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
• Further Results for Perron–Frobenius Theorem for Nonnegative Tensors II
• High-ordered random walks and generalized Laplacians on hypergraphs
• 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?)
• 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 Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory.
• The Eigenvalues of a Graph and Its Chromatic Number
• 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

Cited in

(46)

• Spectral properties of general hypergraphs
• Principal eigenvector of the signless Laplacian matrix
• Spectra of random regular hypergraphs
• Spectral extremal results for hypergraphs
• A Cheeger cut for uniform hypergraphs
• On the Laplacian spectrum of k-uniform hypergraphs
• Random walks and Laplacians on hypergraphs: when do they match?
• Adjacency energy of hypergraphs
• Joins of hypergraphs and their spectra
• The stabilizing index and cyclic index of the coalescence and Cartesian product of uniform hypergraphs
• Adjacency spectra of random and complete hypergraphs
• On the spectrum and number of convex sets in graphs
• Applying a hypergraph to determine the structure of some finite modules
• On some general operators of hypergraphs
• Investigating the connectivity of hypergraphs via their spectra
• Spectrum of mixed bi-uniform hypergraphs
• High-ordered random walks and generalized Laplacians on hypergraphs
• Energies of hypergraphs
• Accessible spectrum of graphs
• Spectra of general hypergraphs
• Spectra of hyperstars
• High-order random walks and generalized Laplacians on hypergraphs
• Core-Periphery Detection in Hypergraphs
• Tensor join of hypergraphs and its spectra
• Some bounds on spectral radius of signless Laplacian matrix of k-graphs
• Cheng's maximal diameter theorem for hypergraphs
• Functional analysis on hypergraphs: density and zeta functions -- applications to molecular graphs and image analysis
• Incidence energy of k-uniform hypertrees
• Normalized Laplacian eigenvalues of hypergraphs
• Coloring outside the lines: spectral bounds for generalized hypergraph colorings
• Bisection width, discrepancy, and eigenvalues of hypergraphs
• On the incidence matrices of hypergraphs
• Understanding high-order network structure using permissible walks on attributed hypergraphs
• A note on Cheeger inequalities for uniform hypergraphs
• Extremal spectral radii of uniform supertrees
• Nodal domain theorems of signed hypergraphs
• Integral uniform hypergraphs
• On the signless Laplacian spectrum of k -uniform hypergraphs
• Faber-Krahn type inequality for supertrees
• Symmetries of hypergraphs and some invariant subspaces of matrices associated with hypergraphs
• On some building blocks of hypergraphs
• Constructing cospectral hypergraphs
• Calculus of variations on hypergraphs
• On Opsut's conjecture for hypercompetition numbers of hypergraphs
• Sombor spectral radius of hypergraphs
• On the spectra of tensor join of 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)