Towards a Spectral Theory for Simplicial Complexes

Abstract

In this dissertation we study combinatorial Hodge Laplacians on simplicial com-plexes using tools generalized from spectral graph theory. Specifically, we considergeneralizations of graph Cheeger numbers and graph random walks. The results inthis dissertation can be thought of as the beginnings of a new spectral theory forsimplicial complexes and a new theory of high-dimensional expansion.We first consider new high-dimensional isoperimetric constants. A new Cheeger-type inequality is proved, under certain conditions, between an isoperimetric constantand the smallest eigenvalue of the Laplacian in codimension 0. The proof is similarto the proof of the Cheeger inequality for graphs. Furthermore, a negative result isproved, using the new Cheeger-type inequality and special examples, showing thatcertain Cheeger-type inequalities cannot hold in codimension 1.Second, we consider new random walks with killing on the set of oriented sim-plexes of a certain dimension. We show that there is a systematic way of relatingthese walks to combinatorial Laplacians such that a certain notion of mixing timeis bounded by a spectral gap and such that distributions that are stationary in acertain sense relate to the harmonics of the Laplacian. In addition, we consider thepossibility of using these new random walks for semi-supervised learning. An algo-rithm is devised which generalizes a classic label-propagation algorithm on graphs tosimplicial complexes. This new algorithm applies to a new semi-supervised learningproblem, one in which the underlying structure to be learned is flow-like.