Many sparse cuts via higher eigenvalues
Joint with Anand Louis, Santosh Vempala and Prasad Raghavendra (moving to Berkeley).
Topic: relating higher eigenvalues of the Laplacian to isopermetric constants.
1. Cheeger inequality
Laplacian is where is the adjacency matrix of the graph and the diagonal degree matrix. The first eigenvalue is , let be the second one.
Cheeger’s inequality deals with Riemannian manifolds. Here is its translation for graphs. Given a subset of vertices, let denote the set of edges between and its complement . Set
There is a weighted variant.
Theorem 1 (Cheeger’s inequality, due to Alon, Alon-Milman, Jerrum-Sinclair) Let be a -regular graph.
Proof: Use min-max characterization of eigenvalues. For reverse inequality, insert Cauchy-Schwarz.
2. Higher eigenvalues
Motivated by Small Set Expansion, a problem introduced by Raghavendra and Steurer in connection with the Unique Games Conjecture.
Unclear a priori what will replace edge expansion.
Theorem 2 Easy: For every disjoint subsets of vertices with, one of them has edge expansion .
Difficult: There exist disjoint subsets with size which all have edge expansion .
Open: Can one replace with exactly .
Tightness: term cannot be avoided (look at noised cube).
Proof is cumbersome but algorithm is nice. James Lee, S. Oveis Gharan and L. Trevisan have an alternate treatment (STOC’12).
Case . Let be an eigenvector. Sort vertices according to increasing . Stop when …
General case. Let be orthonormal eigenvectors. This gives a map to . Pick random Gaussian vectors in . For each vertex ,
– Project along Gaussian directions .
– Pick which maximizes .
– Move (project down) the vector to direction .
Run Cheeger rounding along each direction , output the cuts of expansion .
2.2. Questions from the audience
If one knows that eigenvalues have high multiplicity, can improve on ? Answer: I don’t know.