Abstract

Given a graph G=(V=[n],E), let L be its associated normalized Laplacian matrix and let \lambda_k be the k-th smallest eigenvalue of L. The fundamental Cheeger's Inequality states that \lambda_2 is a quantitative measure of the disconnectivity of the graph, which also provides a theoretical analysis of Fiedler's spectral algorithm for finding a sparse cut. Trevisan proved a variant of Cheeger's Inequality for \lambda_n,  which shows a connection between \lambda_n and the bipartiteness of the graph.

In this talk I will show how to generalize these results further to digraphs, by looking at a class of rotated Laplacian matrices. I will show that its first eigenvalue characterizes the periodicity of the digraph. This provides a unified way to look at these variants of Cheeger's Inequality. In the second part of the talk, I will explain how to apply these observations to design and analyze new spectral algorithms for finding many periodic components, using higher eigenvalues of the rotate Laplacians. This also implies a new higher-order Cheeger-type inequality for periodicity.ty.

Time

Friday, Apr.17, 10:00--11:00

Speaker

Jiyu Zhang

Room

Room 602