On the Houdré-Tetali conjecture about an isoperimetric constant of graphs and Cheeger's inequality

Series
Stochastics Seminar
Time
Thursday, November 21, 2024 - 3:30pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Lap Chi Lau – University of Waterloo – lapchi@uwaterloo.cahttps://cs.uwaterloo.ca/~lapchi/
Organizer
Christian Houdré

Houdré and Tetali defined a class of isoperimetric constants phi_p of graphs for 1/2 <= p <= 1.  When p=1, the classical Cheeger's inequality relates phi_1 to the second smallest eigenvalue of the normalized Laplacian matrix.  Houdré and Tetali conjectured that a similar Cheeger-type inequality holds for p=1/2, which if true would be a strengthening of Cheeger's inequality.  Morris and Peres proved the Houdré-Tetali conjecture up to an additional log factor, using techniques from evolving sets.  In this talk, we discuss the following results about this conjecture:

  - There is a family of counterexamples to the conjecture of Houdré and Tetali, showing that the logarithmic factor is needed.

  - Morris and Peres' result can be recovered using standard spectral arguments. 

  - The Houdré-Tetali conjecture is true for any constant p strictly bigger than 1/2, which is also a strengthening of Cheeger's inequality.

If time permits, we also discuss other strengthenings of Cheeger's inequality.  No background is assumed from the audience.