On Construction of Almost-Ramanujan Graphs

O. Reingold et al. introduced the notion zig-zag product on two different graphs, and presented a fully explicit construction of d-regular expanders with the second largest eigenvalue O(d^-1/3). In the same paper, they ask whether or not the similar technique can be used to construct expanders with the second largest eigenvalue O(d^-1/2). Such graphs are 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 second largest eigenvalue d^{-1/2 + o(1)}, what they call almost-Ramanujan graphs. However, their construction relies on local invertible functions and the dependence between the 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 size will be formalized. By choosing the big graph and several small graphs individually, we shall present a family of fully explicitly almost-Ramanujan graphs with locally invertible function waived.