ON CONSTRUCTION OFALMOST-RAMANUJAN GRAPHS

摘要

O. Reingold et al. introduced the notion zig-zag product on two different graphs, and pre-sented a fully explicit construction of d-regular expanders with the second largest eigen-value 0(d-1/3). In the same paper, they ask whether or not the similar technique can beused to construct expanders with the second largest eigenvalue 0(d-1/2). Such graphsare called Ramanujan graphs. Recently, zig-zag product has been generalized by A. Ben-Aroya and A. Ta-Shma. Using this technique, they present a family of expanders with the 1/2+o(1)second largest eigenvalue d-o(1), what they call almost-Ramanujan graphs. How- ever, their construction relies on local invertible functions and the dependence betweenthe big graph and several small graphs, which makes the construction more complicated.In this paper, we shall give a generalized theorem of zig-zag product. Specifically,the zig-zag product of one "big" graph and several "small" graphs with the same sizewill be formalized. By choosing the big graph and several small graphs individually, weshall present a family of fully explicitly almost-Ramanujan graphs with locally invertiblefunction waived.