%0 Conference Paper %1 Alon %A Alon, Noga %A Milman, V. D. %B 25th Annual Symposium onFoundations of Computer Science, 1984. %D 1984 %I IEEE %K expander graph.theory %P 320--322 %R 10.1109/sfcs.1984.715931 %T Eigenvalues, Expanders And Superconcentrators %X 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.

@inproceedings{Alon, 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.}, added-at = {2016-11-01T04:50:53.000+0100}, author = {Alon, Noga and Milman, V. D.}, biburl = {https://www.bibsonomy.org/bibtex/2158ef87bd8a5c640936f58203d9309fa/ytyoun}, booktitle = {25th Annual Symposium {onFoundations} of Computer Science, 1984.}, doi = {10.1109/sfcs.1984.715931}, interhash = {57dce17b9c81fc0fa919361be228a6a4}, intrahash = {158ef87bd8a5c640936f58203d9309fa}, keywords = {expander graph.theory}, pages = {320--322}, publisher = {IEEE}, timestamp = {2016-11-01T04:50:53.000+0100}, title = {Eigenvalues, Expanders And Superconcentrators}, year = 1984 }