Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Understand

The celebrated Cheeger's Inequality \cite{am85,a86} establishes a bound on the expansion of a graph via its spectrum.

• This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs.
• It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph.
• In this paper we introduce a new hypergraph Laplacian operator (generalizing the Laplacian matrix of graphs)and study its spectra.