期刊
SIAM JOURNAL ON COMPUTING
卷 40, 期 2, 页码 267-290出版社
SIAM PUBLICATIONS
DOI: 10.1137/080732651
关键词
expander graphs; zig-zag product; combinatorial construction
资金
- European Commission [QCS 25596]
- Israel Academy of Sciences and Humanities
- Israel Science Foundation [1090/10]
Reingold, Vadhan, and Wigderson [Ann. of Math. (2), 155 (2002), pp. 157-187] introduced the graph zig-zag product. This product combines a large and a small graph into one, 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 a fully explicit combinatorial construction of 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).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据