Agarwal, Naman ;
Chandrasekaran, Karthekeyan ;
Kolla, Alexandra ;
Madan, Vivek
On the Expansion of GroupBased Lifts
Abstract
A klift of an nvertex base graph G is a graph H on nxk vertices, where each vertex v of G is replaced by k vertices v_1,...,v_k and each edge uv in G is replaced by a matching representing a bijection pi_{uv} so that the edges of H are of the form (u_i,v_{pi_{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 nvertex dregular base graph G, with the nontrivial eigenvalues of the adjacency matrix of G bounded by lambda in magnitude, has the new nontrivial eigenvalues bounded by lambda+O(sqrt{d}) in magnitude with probability 1ke^{Omega(n/d^2)}. The probability bounds as well as the dependency on lambda are almost optimal. As a special case, we obtain that there is a constant c_1 such that for every k<=2^{c_1n/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(sqrt{d}) in magnitude). We also show how this result leads to a quasipolynomial time deterministic algorithm to construct almost Ramanujan expanders.
2. There is a constant c_2 such that for every k>=2^{c_2nd}, there does not exist an abelian klift H of any nvertex dregular base graph such that H is almost Ramanujan. This can be viewed as an analogue of the wellknown noexpansion result for constant degree abelian Cayley graphs.
Suppose k_0 is the order of the largest abelian group that produces expanding lifts. Our two results highlight lower and upper bounds on k_0 that are tight upto a factor of d^3 in the exponent, thus suggesting a threshold phenomenon.
BibTeX  Entry
@InProceedings{agarwal_et_al:LIPIcs:2017:7573,
author = {Naman Agarwal and Karthekeyan Chandrasekaran and Alexandra Kolla and Vivek Madan},
title = {{On the Expansion of GroupBased Lifts}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {24:124:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7573},
URN = {urn:nbn:de:0030drops75739},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.24},
annote = {Keywords: Expanders, Lifts, Spectral Graph Theory}
}
11.08.2017
Keywords: 

Expanders, Lifts, Spectral Graph Theory 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 