Graph-partitioning problems are a central topic of research in
the study of algorithms and complexity theory. They are of interest to
theoreticians with connections to error correcting codes, sampling
algorithms, metric embeddings, among others, and to practitioners, as
algorithms for graph partitioning can be used as fundamental building
blocks in many applications. One of the central problems studied in this
field is the sparsest cut problem, where we want to compute the cut which
has the least ratio of number of edges cut to size of smaller side of the
cut. This ratio is known as the expansion of the cut.
In this talk, I will talk about higher order variants of expansion (i.e.
notions of expansion corresponding to partitioning the graph into more
than two pieces, etc.), and how they relate to the graph’s eigenvalues.
The proofs will also show how to use the graph’s eigenvectors to compute
partitions satisfying these bounds. Based on joint works with Prasad
Raghavendra, Prasad Tetali and Santosh Vempala.