论文标题
来自常规2个expander的横向界限2个扩展器
Transitive bounded-degree 2-expanders from regular 2-expanders
论文作者
论文摘要
如果它的每个边缘都包含在$ d $不同的三角形中，则二维简单复合物称为$ d $ - {\ em常规}。如果$ε$扩展为$ε$，则如果其上下二维随机步行具有标准化的最大特征值，最多是$1-ε$。 在这项工作中，我们介绍了一类有界度的二维扩展器，这是对顶点集合的小2复杂作用的结果。最终的复合物是完全传递的，这意味着自动构成组在其脸上进行了传输。 这样的二维扩展器很少见！这种有界程度的二维扩展器家族的已知构造是从深度代数推理（例如coset几何形状）中获得的。 我们表明，给定一个小$ d $ - 二维$ε$ - expander，存在$ε'=ε'（ε）$和一个有界度的二维简单复合物的家族，具有许多顶点，许多顶点都进入了无限限度，因此每个复杂的属性都满足以下属性：满足以下属性：满足以下属性： *这是$ 4D $ -REGULAL。 *复合物中每个顶点的链接是相同的常规图（直至同构）。 *是$ε'$扩展。 *它是传递的。 如果小型复合物的一板骨骼是完整的多片图，那么我们得到的扩展器家族是明确的，并且在（几乎）一般$ d $ regratular复合物的情况下是随机的。对于随机结构，我们将结果用于简单谎言组的产物中扩展发电机。这种结构的灵感来自于图形锯齿形产品中发生的想法。它可以看作是替换产品的二维类似物。
A two-dimensional simplicial complex is called $d$-{\em regular} if every edge of it is contained in exactly $d$ distinct triangles. It is called $ε$-expanding if its up-down two-dimensional random walk has a normalized maximal eigenvalue which is at most $1-ε$. In this work, we present a class of bounded degree 2-dimensional expanders, which is the result of a small 2-complex action on a vertex set. The resulted complexes are fully transitive, meaning the automorphism group acts transitively on their faces. Such two-dimensional expanders are rare! Known constructions of such bounded degree two-dimensional expander families are obtained from deep algebraic reasonings (e.g. coset geometries). We show that given a small $d$-regular two-dimensional $ε$-expander, there exists an $ε'=ε'(ε)$ and a family of bounded degree two-dimensional simplicial complexes with a number of vertices goes to infinity, such that each complex in the family satisfies the following properties: * It is $4d$-regular. * The link of each vertex in the complex is the same regular graph (up to isomorphism). * It is $ε'$ expanding. * It is transitive. The family of expanders that we get is explicit if the one-skeleton of the small complex is a complete multipartite graph, and it is random in the case of (almost) general $d$-regular complex. For the randomized construction, we use results on expanding generators in a product of simple Lie groups. This construction is inspired by ideas that occur in the zig-zag product for graphs. It can be seen as a loose two-dimensional analog of the replacement product.
