** 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

and

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).

** 2.1. Algorithm **

**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.

### Like this:

Like Loading...

*Related*

## About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri PoincarĂ©, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
http://www.math.ens.fr/metric2011/