High-Dimensional Expanders from Expanders

DOI10.4230/LIPICS.ITCS.2020.12MaRDI QIDQ6322653arXivFDO

Authors Si-Qi Liu, Sidhanth Mohanty, Elizabeth Yang

Publication date 24 July 2019

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Expander graphs (05C48)

Abstract: We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to the stationary distribution. As an upshot, we obtain new constructions, as well as a natural probabilistic model to sample constant degree high-dimensional expanders. In particular, we show that given an expander graph $G$, adding self loops to $G$ and taking the tensor product of the modified graph with a high-dimensional expander produces a new high-dimensional expander. Our proof of rapid mixing of high order random walks is based on the decomposable Markov chains framework introduced by Jerrum et al.

Recommendations

• High dimensional random walks and colorful expansion
• High order random walks: beyond spectral gap
• Simplicial complexes: spectrum, homology and random walks
• High order random walks: beyond spectral gap
• Construction of new local spectral high dimensional expanders

Cited in

(6)

• High order random walks: beyond spectral gap
• Simplicial complexes: spectrum, homology and random walks
• High dimensional random walks and colorful expansion
• High order random walks: beyond spectral gap
• Expanders and dimensional expansion
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps

This page was built for publication: High-Dimensional Expanders from Expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322653)