High-Dimensional Expanders from Expanders

We present an elementary way to transform an expander graphinto a simplicial complex where all high order random walks have 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 [JST+04]. In this talk we will present the construction, prove the local and global expansions and give the general proof idea of rapid mixing of high order random walks. [Joint work w/ Sidhanth Mohanty, Elizabeth Yang]