Name
Abstract | ||
|---|---|---|
Random walks on expander graphs have been extensively studied. We define a high order combinatorial random walk on high dimensional simplicial complexes. This walk moves at random between neighboring i-dimensional faces (e.g. edges) of the complex, where two i-dimensional faces are considered neighbors if they share a common (i + 1)-dimensional face (e.g. a triangle). We prove that if the links of the complex are good spectral expanders, then the high order combinatorial random walk converges quickly. We derive our result about the convergence of the high order random walk by defining a new notion of high dimensional combinatorial expansion of a complex, which we term colorful expansion. We show that spectral expansion of the links of the complex imply colorful expansion of the complex, which in turn implies fast convergence of the high order random walk. We further show the existence of bounded degree high dimensional simplicial complexes which satisfy our criterion, and thus form an explicit family of high dimensional simplicial complexes in which the high order random walk converges rapidly. Our high order combinatorial random walk is different than the high order topological random walk that has recently been defined in [PR]. The topological random walk is associated with the concentration of the spectrum of the high order laplacian on the space that is orthogonal to the coboundaries, while we, in a sense, need to argue about the concentration of the spectrum on the space that is orthogonal to the constant functions, which is a much larger space. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Computational Complexity | Self-avoiding walk,Discrete mathematics,Loop-erased random walk,Combinatorics,Expander graph,Random walk,Constant function,Heterogeneous random walk in one dimension,Mathematics,Bounded function,Laplace operator |
DocType | Volume | Citations |
Journal | abs/1604.02947 | 3 |
PageRank | References | Authors |
0.49 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tali Kaufman | 1 | 499 | 38.33 |
| David Mass | 2 | 5 | 2.97 |