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, . . ., v_k 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(d) in magnitude with probability 1 − ke−Ω(^{n/d 2)}. The probability bounds as well as the dependency on λ are almost optimal. As a special case, we obtain that there is a constant c₁ such that for every k ≤ 2^c1 ^{n/d 2} , 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(d) in magnitude). This result leads to a quasi-polynomial time deterministic algorithm to construct almost Ramanujan expanders; 2. there is a constant c₂ such that for every k ≥ 2^{c 2 nd}, 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 nonexpansion result for constant degree abelian Cayley graphs. Suppose k₀ is the order of the largest abelian group that produces expanding lifts. Our two results highlight lower and upper bounds on k₀ that are tight up to a factor of d³ in the exponent, thus suggesting a threshold phenomenon.