Towards a Spectral Theory for Simplicial Complexes

In this dissertation we study combinatorial Hodge Laplacians on simplicial com-

plexes using tools generalized from spectral graph theory. Specifically, we consider

generalizations of graph Cheeger numbers and graph random walks. The results in

this dissertation can be thought of as the beginnings of a new spectral theory for

simplicial 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 constant

and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar

to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is

proved, using the new Cheeger-type inequality and special examples, showing that

certain 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 relating

these walks to combinatorial Laplacians such that a certain notion of mixing time

is bounded by a spectral gap and such that distributions that are stationary in a

certain sense relate to the harmonics of the Laplacian. In addition, we consider the

possibility of using these new random walks for semi-supervised learning. An algo-

rithm is devised which generalizes a classic label-propagation algorithm on graphs to

simplicial complexes. This new algorithm applies to a new semi-supervised learning

problem, one in which the underlying structure to be learned is flow-like.