On the expansion of group-based lifts

DOI10.1137/17M1141047MaRDI QIDQ5232157zbMATH OpenFDO

Authors Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan

Publication date 29 August 2019

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

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

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

Abstract: A

k

-lift of an

n

-vertex base graph

G

is a graph

H

on

n i m e s k

vertices, where each vertex

v

of

G

is replaced by

k

vertices

v_{1}, c d o t s, v_{k}

and each edge

(u, v)

in

G

is replaced by a matching representing a bijection

p i_{u v}

so that the edges of

H

are of the form

(u_{i}, v_{p i_{u v} (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

k g e q 2^{c_{1} n d}

, 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 (s q r t d)

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

l a m b d a

in magnitude, has the new nontrivial eigenvalues also bounded by

l a m b d a + O (s q r t d)

in magnitude with probability

1 - k e^{- O m e g a (n / d^{2})}

. In particular, there is a constant

c_{2}

such that for every

k l e q 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).

Recommendations

Cites work

Cited in

(8)

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)