Semi-direct product in groups and zig-zag product in graphs: connections and applications
Authors:
- A. LubotzkyALA. Lubotzky
- A. WigdersonAWA. Wigderson
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 630-637
Abstract
We consider the standard semi-direct product A/spl times/B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A/spl times/B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of O. Reingold et al. (2000), 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. A. Lubotzky and B. Weiss (1993) asked whether expansion is a group property; namely, is being an 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 the negative, by showing an infinite family of groups A/sub i//spl times/B/sub i/ which are expanders with one choice of a (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 S/sub n/ or the simple groups PSL(2, p).Keywords
This publication has 12 references indexed in Scilit:
- Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors2002
- Expansion Properties of Cayley Graphs of the Alternating GroupsJournal of Combinatorial Theory, Series A, 1997
- Random Cayley graphs and expandersRandom Structures & Algorithms, 1994
- Fast Fourier Analysis for SL2over a Finite Field and Related Numerical ExperimentsExperimental Mathematics, 1992
- Ramanujan graphsCombinatorica, 1988
- Eigenvalues and expandersCombinatorica, 1986
- ARTIN'S CONJECTURE FOR PRIMITIVE ROOTSThe Quarterly Journal of Mathematics, 1986
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- Limitations on Explicit Constructions of Expanding GraphsSIAM Journal on Computing, 1984
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981