Sharp Poincare and log-Sobolev Inequalities for the Switch Chain on Regular Bipartite Graphs

on YouTube ↗57m

" summary

Proves the Poincaré (spectral gap) constant for the switch chain on simple d-regular bipartite graphs is Theta(n d) under mild growth assumptions on d (allows d → ∞ up to a tiny power of n), and derives near-optimal mixing bounds; constant-d regime yields a log-Sobolev bound giving mixing O(n log^2 n). Argument compares to the configuration model, builds a randomized harmonic extension by averaging over S-neighborhoods and adding Gaussian-controlled fluctuations, and finishes with a canonical-path comparison.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 3:52Simple switching
3. 6:07The switch chain on bipartite graphs
4. 9:46The relaxation time and the Poincaré inequality
5. 10:39Mixing and relaxation times
6. 13:11The problem
7. 19:00Comparison to the configuration model
8. 20:44Switch chains on simple graphs: overview of literature
9. 25:01The canonical path method
10. 27:43A main result
11. 29:41The approach
12. 33:17Issues with the harmonic extension
13. 36:48Simple paths and s-neighborhoods
14. 40:06A Gaussian field on 29(d)
15. 48:05Definition of f (commentary)
16. 51:27Estimating the Dirichlet form (continued)
17. 51:46The log-Sobolev inequality for constant d