arXiv preprint ·
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders. One of the most striking results in this burgeoning literature is that a spectral gap for the global down-up walk on the facets of a pure simplicial complex can be reduced to sufficiently strong spectral expansion of just the codimension-2 links of the complex, a phenomenon colloquially referred to as "trickle-down". These types of theorems have had many important applications, including rapid mixing of the exchange walk on the bases of any matroid. In this primarily expository article, we give streamlined proofs of two such theorems in the literature, one by Oppenheim (2018) and one by Leake and Oveis Gharan (2025), via an integrated Bochner method. Moreover, in the latter setting, we quantitatively strengthen the dependence of the global spectral gap on the dimension of the complex and the spectral influence, resolving an open question of Leake and Oveis Gharan. Disclaimer: The proofs were developed through a couple of rounds of interaction with GPT-5.6 Sol Ultra. We later discovered that Guo and Zhang (2026) had independently proven the same strengthening of the trickle-down theorem of Leake and Oveis Gharan using an extremely similar argument, also found by GPT-5.6 Sol Ultra. The focus of their paper is the complexity of approximating the partition function of spin systems on planar graphs, not on the trickle-down phenomenon itself. In contrast, our motivation is primarily expository, and we hope to bring Bochner-type methods and their connections with the trickle-down phenomenon to the attention of a wider community of researchers.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Improved Algorithms for Beck--Fiala with Bounded Sets
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
Integrality gap preserving reductions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.