On the expansion of group-based lifts

DOI10.1137/17M1141047zbMATH Open1419.05119arXiv1311.3268MaRDI QIDQ5232157FDOQ5232157

Vivek Madan, Karthekeyan Chandrasekaran, Alexandra Kolla, Naman Agarwal

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A $k$-lift of an $n$-vertex base graph $G$ is a graph $H$ on $nimesk$ vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices $v_1,cdots,v_k$ and each edge $(u,v)$ in $G$ is replaced by a matching representing a bijection $p{i}_{uv}$ so that the edges of $H$ are of the form $(u_i,v_{p{i}_{uv}(i)})$. Lifts have been studied 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) There is a constant $c_1$ such that for every $kgeq{2}^{c_{1}nd}$, there does not exist an abelian $k$-lift $H$ of any $n$-vertex $d$-regular base graph with $H$ being almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most $O(sqrtd)$ in magnitude). This can be viewed as an analogue of the well-known no-expansion result for abelian Cayley graphs. (2) A uniform random lift in 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 $lambda$ in magnitude, has the new nontrivial eigenvalues also bounded by $lambda+O(sqrtd)$ in magnitude with probability $1-k{e}^{-Omega(n/d^2)}$. In particular, there is a constant $c_2$ such that for every $kleq{2}^{c_{2}n/d^2}$, there exists a lift $H$ of every Ramanujan graph in a cyclic group of order $k$ with $H$ being almost Ramanujan. We use this to design a quasi-polynomial time algorithm to construct almost Ramanujan expanders deterministically. The existence of expanding lifts in cyclic groups of order $k=2^{O(n/d^2)}$ can be viewed as a lower bound on the order $k_0$ of the largest abelian group that produces expanding lifts. Our results show that the lower bound matches the upper bound for $k_0$ (upto $d^3$ in the exponent).

Full work available at URL: https://arxiv.org/abs/1311.3268

Recommendations

• On the expansion of group-based lifts
• Spectra of lifted Ramanujan graphs
• Lifts, discrepancy and nearly optimal spectral gap
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• Random lifts of graphs

zbMATH Keywords

expandersRamanujan graphsrandom lifts

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Expander graphs and their applications
• Lifts, discrepancy and nearly optimal spectral gap
• Ramanujan graphs
• Characteristic polynomials of some graph coverings
• A proof of Alon’s second eigenvalue conjecture and related problems
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On the second eigenvalue of a graph
• Diameters and Eigenvalues
• Word maps and spectra of random graph lifts
• Spectra of lifted Ramanujan graphs
• Title not available (Why is that?)
• Relative expanders or weakly relatively Ramanujan graphs.
• Characteristic polynomials of graph coverings
• Spectral estimates for abelian Cayley graphs
• Shift lifts preserving Ramanujan property
• Ramanujan coverings of graphs

Cited In (1)

• Covers, orientations and factors

This page was built for publication: On the expansion of group-based lifts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232157)