## Speaker:

## Affiliation:

California Institute of Technology

Department of Computer Science

1200 E Calfornia Blvd|

Pasadena, CA 91125

United States of America

## Time:

## Venue:

- A-201 (STCS Seminar Room)

## Organisers:

Cheeger inequalities in spectral graph theory help to comment on the approximate connectivity or expansion of a graph (a combinatorial property) from the eigenvalues of the adjacency matrix of the graph (an algebraic property). More specifically, it says that the expansion of a graph can be tightly bound by the second largest eigenvalue of the graph. The Cheeger inequalities were generalized by Lee-Gharan-Trevisan so that the k-way expansion of a graph can be approximated by the k largest eigenvalues of the adjacency matrix.

In this talk, i will present the higher order cheeger inequality, which roughly says, that the first k eigenvalues of the laplacian of a graph are close to 0 if and only if we can find k approximately disjoint subsets in the graph. I will start with the basics and show the inequality.

Paper: https://arxiv.org/abs/1111.1055