High Dimensional Random Walks and Colorful Expansion
High Dimensional Random Walks and Colorful Expansion
复制标题
高维随机游走和彩色展开
DOI：
10.4230/lipics.itcs.2017.4
复制
发表时间：
2016
影响因子：
1.4
通讯作者：
David Mass
中科院分区：
文献类型：
--
作者：
T. Kaufman;David Mass
在有限程度的扩展器图上随机行走具有许多应用，无论是在理论和实践计算问题中。这些步行的关键特性是它们迅速融合到固定分布。
在这项工作中，我们{\ em定义了高阶随机步行}：这些是图形上随机步行的概括，即高维纯种复合物，它们是图形的高维类似物。尺寸的简单复合物$ d $具有顶点，边缘，三角形，金字塔，最多$ d $二维的单元格。对于任何$ 0 \ leq i <d $，在尺寸$ i $上进行的高级随机步行$ i $在邻近的$ i $ faces（例如边缘）之间，如果他们共享，则两个$ i $ - faces被视为邻居一个常见的$（i+1）$ - 面（例如，三角形）。 $ i = 0 $的情况恢复了所研究的随机步行图。
我们在一个复合体上提供了一个{\ em局部到全球标准}，这意味着在其上{\ em em快速收敛}。具体而言，我们证明，如果复杂链接的所有链接的$ 1 $维骨架是光谱展开器，那么对于{\ em all} $ 0 \ le i <d $ high Or-i <d $ the dimension $ i $上的高级随机步行$ i $迅速收敛到其固定分布。
我们通过对复合物的高维组合扩展的新概念得出结果，我们将其称为{\ em彩色扩展}。该概念是图形组合扩展的自然概括，并且与高阶随机步行的收敛速率密切相关。
我们进一步展示了满足该标准的{\ em有限程度}复合体的明确家族。具体而言，我们表明Ramanujan综合体符合此标准，因此形成了一个有界程度的显式家族，高尺寸的简单络合物，其中所有高级随机步行都迅速融合到它们的固定分布。
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 {\em 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 $d$-dimensional cells. For any $0 \leq i < d$, a high order random walk on dimension $i$ moves between neighboring $i$-faces (e.g., edges) of the complex, where two $i$-faces 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 {\em local-to-global criterion} on a complex which implies {\em rapid convergence of all high order random walks} on it. Specifically, we prove that if the $1$-dimensional skeletons of all the links of a complex are spectral expanders, then for {\em 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 {\em 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 {\em 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.
DOI：
10.4171/owr/2016/46
发表时间：
2016
期刊：
Oberwolfach Reports
影响因子：
--
作者：
Loeser F
通讯作者：
Loeser F