Eigenvalues, Expanders And Superconcentrators
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 320-322
- https://doi.org/10.1109/sfcs.1984.715931
Abstract
Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. There is essentially only one known explicit construction. Here we show a correspondence between the eigenvalues of the adjacency matrix of a graph and its expansion properties, and combine it with results on Group Representations to obtain many new examples of families of linear expanders. We also obtain better expanders than those previously known and use them to construct explicitly n-superconcentrators with 157.4 n edges, much less than the previous most economical construction.Keywords
This publication has 15 references indexed in Scilit:
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- Advances in pebblingPublished by Springer Nature ,1982
- Non-existence of one-dimensional expanding graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Time-space tradeoffs for computing functions, using connectivity properties of their circuitsJournal of Computer and System Sciences, 1980
- Time-space tradeoffs for some algebraic problemsPublished by Association for Computing Machinery (ACM) ,1980
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking NetworksBell System Technical Journal, 1979
- A note on a construction of MargulisInformation Processing Letters, 1979
- SuperconcentratorsSIAM Journal on Computing, 1977
- Space bounds for a game on graphsTheory of Computing Systems, 1976