Abstract
Approximating expansion of small sets in graphs is a computational problem of great interest due to its connections to the unique games conjecture. In this talk, we will survey some recent developments that connect the spectrum of graphs to edge expansion of small sets in them. Specifically, we will discuss the following results:
- Higher Order Cheeger Inequalities: These are analogues of the classical Cheeger's inequality that connect the higher eigenvalues of the graph to the corresponding combinatorial problem of decomposing a graph in to several sets of small sparsity. In turn, these yield a direct connection between higher eigenvalues and expansion of small sets in graphs.
- Graphs with Large Threshold Rank: The complexity of small set expansion problem is directly tied to the number of large eigenvalues of the graph. In fact, for the small set expansion to be computationally intractable, there must exist small set expanders that have up to polynomially many large eigenvalues. While the existence of such graphs still remains open, a recent construction called the `short code' achieves quasi polynomially many eigenvalues. This is achieved by creating a subgraph of the noisy hypercube graph that inherits the spectral and hypercontractive properties but is on much fewer vertices.