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. We prove a Cheeger-type
inequality for hypergraphs, relating the second smallest eigenvalue of this
operator to the expansion of the hypergraph. We bound other hypergraph
expansion parameters via higher eigenvalues of this operator. We give bounds on
the diameter of the hypergraph as a function of the second smallest eigenvalue
of the Laplacian operator. The Markov process underlying the Laplacian operator
can be viewed as a dispersion process on the vertices of the hypergraph that
might be of independent interest. We bound the {\em Mixing-time} of this
process as a function of the second smallest eigenvalue of the Laplacian
operator. All these results are generalizations of the corresponding results
for graphs.
We show that there can be no linear operator for hypergraphs whose spectra
captures hypergraph expansion in a Cheeger-like manner. For any $k$, we give a
polynomial time algorithm to compute an approximation to the $k^{th}$ smallest
eigenvalue of the operator. We show that this approximation factor is optimal
under the SSE hypothesis (introduced by \cite{rs10}) for constant values of
$k$.
Finally, using the factor preserving reduction from vertex expansion in
graphs to hypergraph expansion, we show that all our results for hypergraphs
extend to vertex expansion in graphs.

本文引入了一种新的超图拉普拉斯算子，并研究了其光谱。通过该算子的第二小本征值，证明了超图的扩展性和混合时间，并进一步将这些结果推广到了图的节点扩展。