Explicit Concentrators from Generalized N-Gons
- 1 September 1984
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 5 (3) , 287-293
- https://doi.org/10.1137/0605030
Abstract
Summary:We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negativeThis publication has 9 references indexed in Scilit:
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981
- Explicit constructions of linear size superconcentratorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Generalized ConnectorsSIAM Journal on Computing, 1978
- Complexity TheoryScientific American, 1978
- SuperconcentratorsSIAM Journal on Computing, 1977
- On non-linear lower bounds in computational complexityPublished by Association for Computing Machinery (ACM) ,1975
- Algebraic Graph TheoryPublished by Cambridge University Press (CUP) ,1974
- Finite GeometriesPublished by Springer Nature ,1968
- The nonexistence of certain generalized polygonsJournal of Algebra, 1964