Hypergraph Heat Operators and Eigenvalues

Graph and hypergraph partitioning problems are a central topic of research in the study of algorithms and complexity theory, with connections to sampling algorithms, mixing time of Markov chains, metric embeddings, among others. There has been a lot of work studying the eigenvalues of a graph and relating it to combinatorial properties of the graph. 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.

I will define a Markov operator for hypergraphs which generalizes the heat kernel for graphs (similar to the Random Walk operator). I will demonstrate the utility of this operator by showing generalizations of some known results from spectral graph theory to hypergraphs; for e.g. bounding various hypergraph expansion parameters via eigenvalues bounding the diameter of the hypergraph, mixing time of this operator, etc.