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.
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License.
Rights for Collection: Duke Dissertations