High-Dimensional Expanders from Expanders

DOI10.4230/LIPICS.ITCS.2020.12zbMATH Open1522.05270arXiv1907.10771MaRDI QIDQ6322653FDOQ6322653

Authors: Si-Qi Liu, Sidhanth Mohanty, Elizabeth Yang 

Publication date: 24 July 2019

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

Mathematics Subject Classification ID

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

Cited In (1)

• Expanders and dimensional expansion

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)