Abstract

Given a graph G=(V=[n],E), let L be its associated normalized Laplacian matrix and let be the k-th smallest eigenvalue of L. The fundamental Cheeger's Inequality states that 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 ,, which shows a connection between , 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.

Time

2026-04-28, 10:00 - 11:00

Speaker

Jiyu Zhang, Bocconi University

Room

Room 602