Abstract

The classical Cheever'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 optimal assuming the small-set expansion conjecture, and generalize it to the weighted setting, answering an open question posed by them. Building on this connection, we discover that several interesting generalizations of Cheever's inequality relating edge conductance and eigenvalues have a close analog in relating vertex expansions and reweighed eigenvalues.

This is based on joint work with Lap Chi Lau and Kam Chuen Tung.

Time

2022-06-21  13:30 - 14:30   

Speaker

Tsz Chiu Kwok,  ITCS@SUFE

Room

Tencent meeting ID: 853-8759-9058; PW: 123456