TY - JOUR

T1 - Semi-direct product in groups and zig-zag product in graphs

T2 - Connections and applications

AU - Alon, Noga

AU - Lubotzky, Alexander

AU - Wigderson, Avi

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2001

Y1 - 2001

N2 - We consider the standard semi-direct product A × B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A × B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of [RVW00], the new Cayley graph is an expander if and only if its two components are. We develop some general ways of using this construction to obtain large constant-degree expanding Cayley graphs from small ones. In [LW93], Lubotzky and Weiss asked whether expansion is a group property; namely, is being expander for (a Cayley graph of) a group G depend solely on G and not on the choice of generators. We use the above construction to answer the question in negative, by showing an infinite family of groups Ai × Bi which are expanders with one choice of (constant-size) set of generators and are not with another such choice. It is interesting to note that this problem is still open, though, for "natural" families of groups, like the symmetric groups Sn or the simple groups PSL(2, p).

AB - We consider the standard semi-direct product A × B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A × B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of [RVW00], the new Cayley graph is an expander if and only if its two components are. We develop some general ways of using this construction to obtain large constant-degree expanding Cayley graphs from small ones. In [LW93], Lubotzky and Weiss asked whether expansion is a group property; namely, is being expander for (a Cayley graph of) a group G depend solely on G and not on the choice of generators. We use the above construction to answer the question in negative, by showing an infinite family of groups Ai × Bi which are expanders with one choice of (constant-size) set of generators and are not with another such choice. It is interesting to note that this problem is still open, though, for "natural" families of groups, like the symmetric groups Sn or the simple groups PSL(2, p).

UR - http://www.scopus.com/inward/record.url?scp=0035181247&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035181247&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2001.959939

DO - 10.1109/SFCS.2001.959939

M3 - Article

AN - SCOPUS:0035181247

SN - 0272-5428

SP - 630

EP - 637

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

ER -