A combinatorial construction of almost-ramanujan graphs using the zig-zag product
A combinatorial construction of almost-ramanujan graphs using the zig-zag product
复制标题
使用 zig-zag 产品组合构造近拉马努金图
DOI：
10.1145/1374376.1374424
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Avraham Ben;A. Ta
Reingold，Vadhan和Wigderson [21]引入了图之字形积。该产品将一个大型图和一个小型图组合成一个图，使得所得到的图从大型图继承其大小，从小型图继承其度，并且从两者继承其谱间隙。使用这个产品，他们给出了扩展图的第一个完全明确的组合构造。他们展示了如何构造具有谱隙1-O（D-1/3）的D-正则图。在同一篇论文中，他们提出了一个公开的问题，即是否可以使用类似的图积来实现几乎最优的谱隙1-O（D-1/2）。在本文中，我们提出了一个推广的zig-zag产品，结合了一个大的图和几个小的图。新的产品给出了一个更好的关系之间的程度和频谱间隙的结果图。我们利用新的积给出了具有谱隙1-D-1/2 + o（1）的D-正则图的一个完全显式的组合构造。
Reingold, Vadhan and Wigderson [21] introduced the graph zig-zag product. This product combines a large graph and a small graph into one graph, such that the resulting graph inherits its size from the large graph, its degree from the small graph and its spectral gap from both. Using this product they gave the first fully-explicit combinatorial construction of expander graphs. They showed how to construct D-regular graphs having spectral gap 1-O(D-1/3). In the same paper, they posed the open problem of whether a similar graph product could be used to achieve the almost-optimal spectral gap 1-O(D-1/2). In this paper we propose a generalization of the zig-zag product that combines a large graph and several small graphs. The new product gives a better relation between the degree and the spectral gap of the resulting graph. We use the new product to give a fully-explicit combinatorial construction of D-regular graphs having spectral gap 1-D-1/2 + o(1).