On the expansion of group-based lifts

A k-lift of an n-vertex base graph G is a graph H on n × k vertices, where each vertex v of G is replaced by k vertices v1, . . . , vk and each edge uv in G is replaced by a matching representing a bijection φuv so that the edges of H are of the form (ui, vφuv(i)). Lifts have been investigated as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are: 1. A uniform random lift by a cyclic group of order k of any n-vertex d-regular base graph G, with the nontrivial eigenvalues of the adjacency matrix of G bounded by λ in magnitude, has the new nontrivial eigenvalues bounded by λ + O( p d) in magnitude with probability 1 - ke- (n/d2). The probability bounds as well as the dependency on λ are almost optimal. As a special case, we obtain that there is a constant c1 such that for every k 2c1n/d2 , there exists a lift H of every Ramanujan graph by a cyclic group of order k such that H is almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most O( p d) in magnitude). We also show how this result leads to a quasi-polynomial time deterministic algorithm to construct almost Ramanujan expanders. 2. There is a constant c2 such that for every k λ 2c2nd, there does not exist an abelian k-lift H of any n-vertex d-regular base graph such that H is almost Ramanujan. This can be viewed as an analogue of the well-known no-expansion result for constant degree abelian Cayley graphs. Suppose k0 is the order of the largest abelian group that produces expanding lifts. Our two results highlight lower and upper bounds on k0 that are tight upto a factor of d3 in the exponent, thus suggesting a threshold phenomenon.