- 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.ca – https://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.