Tata Institute of Fundamental Research
Higher Order Cheeger Inequalities
Seminar
Speaker:
Jenish Mehta (California Institute of Technology
Department of Computer Science
1200 E Calfornia Blvd|
Pasadena, CA 91125
United States of America)
Organiser:
Varun Narayanan
Date:
Friday, 12 Aug 2016, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Jenish Mehta (California Institute of Technology Department of Computer Science 1200 E Calfornia Blvd| Pasadena, CA 91125 United States of America) |
| Organiser: | Varun Narayanan |
| Date: | Friday, 12 Aug 2016, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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
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