high dimensional combinatorial expansion of complexes which we term [*colorful expansion*]{}. This notion is a natural generalization of combinatorial expansion of graphs and is strongly related to the convergence rate of the high order random walks.

    We further show an explicit family of [*bounded degree*]{} complexes which satisfy this criterion. Specifically, we show that Ramanujan complexes meet this criterion, and thus form an explicit family of bounded degree high dimensional simplicial complexes in which all of the high order random walks converge rapidly to their stationary distribution.
author:
- 'Tali Kaufman[^1]'
- 'David Mass[^2]'
title: High Dimensional Random Walks and Colorful Expansion
---

Introduction
============

Expander graphs play a fundamental role in computer science, mathematics, physics and more (see e.g. [@HLW06] and [@Lub12]). In particular, random walks on bounded degree expander graphs have been proven very useful for many applications. A key property of these walks is that they converge rapidly to their stationary distribution. This property allows one to efficiently sample points from some huge space while investing only a few random bits, which is necessary in many theoretical and practical computational problems.

In recent years a generalization of expander graphs to higher dimensions has emerged. The high dimensional 