Back to Search
Start Over
Discrepancy and Eigenvalues of Cayley Graphs
- Source :
- Czech. Math. J. 66(3), 2016, 941-954
- Publication Year :
- 2016
-
Abstract
- 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 positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.<br />Comment: Dedicated to the memory of Professor Miroslav Fiedler, 33 pages, second version addresses changes arising from the referee report and includes an appendix with an earlier argument
- Subjects :
- Mathematics - Combinatorics
Primary: 05C50. Secondary: 05C80
Subjects
Details
- Database :
- arXiv
- Journal :
- Czech. Math. J. 66(3), 2016, 941-954
- Publication Type :
- Report
- Accession number :
- edsarx.1602.02291
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s10587-016-0302-x