Random Walks on Simplicial Complexes and Isoperimetric Inequalities
summary
Extends spectral graph ideas to simplicial complexes by working with the Hodge Laplacian and defining concrete up/down random walks on oriented k‑cells; constructs Markov matrices that double each cell (two orientations) and add a death state for Dirichlet behavior; proves a Cheeger inequality for chains on orientable pseudomanifolds but gives a counterexample using stellar subdivision where coboundary (cochain) isoperimetric constants and eigenvalues decay at wildly different rates; shows lazy walks converge to harmonics when cohomology is trivial and flags open problems like irreducibility and the continuum limit.
AI-written summary · about
chapters (28)
- 0:00Intro
- 1:50Laplacian eigenmaps
- 3:18Label propogation
- 5:15Cheeger inequality for graphs
- 6:02Edge expansion
- 6:40Harmonic functions and walks
- 7:24Sensor network coverage
- 9:40Near one homology
- 11:51Related work
- 15:25Chains and cochains
- 19:31Hodge Laplacian
- 21:32Combinatorial Laplacian
- 24:58Cheeger numbers on cochains
- 26:51Recovering the graph Laplacian
- 27:18Negative result on cochains
- 27:49Cheeger part
- 29:20Boundary hypothesis
- 31:55Random walks on graphs
- 33:20Walk corresponding to down
- 35:02Geometry of Dirichlet k-walk
- 36:35Geometry of the random walk
- 37:38Propagation matrix
- 39:41Spectral analysis of walk
- 40:23Edge propagation
- 40:51Contrasting walks
- 41:30Contrasting walis
- 41:51Open problems
- 42:50Acknowledgements
related talks
01h 05mRandom Walks on Simplicial Complexes for Exploring Networks
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
58mTools from Stochastic Calculus 1
01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...
01h 03mSampling Crash Course
32mLocal Statistics, Semidefinite Programming, and Community Detection
19mProbabilistic programming interfaces for random graphs: Markov categories, graph...
49mRecent Advances in Counting Sparse Graphs