On the spectrum of hypergraphs

Anirban Banerjee

Published 2017-11-26Version 1

Hypergraphs are well represented by hypermatrices (tensors) and are extensively studied by the eigenvalues of these hypermatrices. Due to higher order nonlinear equations, their eigenvalues are not easy to compute and it makes the study of spectral theory of hypergraphs difficult. Here, we introduce adjacency, Laplacian and normalized Laplacian matrices of uniform hyperhraphs. We show that different structural properties of hypergrpahs, like, diameter, vertex strong chromatic number, Cheeger constant, etc., can also be well studied using spectral properties of these matrices. Random walk on a hyper graph can be explored by using the spectrum of transition probability operator defined on the hypergraph. We also introduce Ricci curvature(s) on hypergraphs and show that if the Laplace operator, $\Delta$, on a hypergraph satisfies a curvature-dimension type inequality $CD (\mathbf{m}, \mathbf{K})$ with $\mathbf{m}>1 $ and $\mathbf{K}>0 $ then any non-zero eigenvalue of $- \Delta$ can be bounded bellow by $ \frac{ \mathbf{m} \mathbf{K} }{ \mathbf{m} -1 } $. Eigenvalues of a normalized Laplacian operator defined on a connected hypergraph can be bounded by the Ollivier's Ricci curvature of the hypergraph.