PhD Seminar • Algorithms and Complexity • Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Please note: This PhD seminar will take place in DC 2310.

Kam Chuen (Alex) Tung, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Lap Chi Lau

The classical Cheeger’s inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality connecting the vertex expansion of a graph and the maximum reweighted second smallest eigenvalue of the Laplacian matrix.

In this work, we first improve their result to a logarithmic dependence on the maximum degree in the graph, which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include an analog of Trevisan’s result on bipartiteness, an analog of higher order Cheeger’s inequality, and an analog of improved Cheeger’s inequality.

Finally, inspired by this connection, we present negative evidence to the 0/1-polytope edge expansion conjecture by Mihail and Vazirani. We construct 0/1-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these 0/1-polytopes is almost linear in the graph size.

This talk is based on a joint paper with Tsz Chiu Kwok and Lap Chi Lau. The paper can be accessed at https://arxiv.org/abs/2203.06168.