Kaufman, Tali ;
Mass, David
High Dimensional Random Walks and Colorful Expansion
Abstract
Random walks on bounded degree expander graphs have numerous applications, both in theoretical and practical computational problems. A key property of these walks is that they converge rapidly to their stationary distribution.
In this work we define high order random walks: These are generalizations of random walks on graphs to high dimensional simplicial complexes, which are the high dimensional analogues of graphs. A simplicial complex of dimension d has vertices, edges, triangles, pyramids, up to ddimensional cells. For any 0 \leq i < d, a high order random walk on dimension i moves between neighboring ifaces (e.g., edges) of the complex, where two ifaces are considered neighbors if they share a common (i+1)face (e.g., a triangle). The case of i=0 recovers the well studied random walk on graphs.
We provide a localtoglobal criterion on a complex which implies rapid convergence of all high order random walks on it. Specifically, we prove that if the 1dimensional skeletons of all the links of a complex are spectral expanders, then for all 0 \le i < d the high order random walk on dimension i converges rapidly to its stationary distribution.
We derive our result through a new notion of 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.
BibTeX  Entry
@InProceedings{kaufman_et_al:LIPIcs:2017:8183,
author = {Tali Kaufman and David Mass},
title = {{High Dimensional Random Walks and Colorful Expansion}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {4:14:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8183},
URN = {urn:nbn:de:0030drops81838},
doi = {10.4230/LIPIcs.ITCS.2017.4},
annote = {Keywords: High dimensional expanders, expander graphs, random walks}
}
28.11.2017
Keywords: 

High dimensional expanders, expander graphs, random walks 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

28.11.2017 