Discrepancy and eigenvalues of Cayley graphs

Yoshiharu Kohayakawa, Vojtěch Röd and Mathias Schacht

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 negative.

The whole paper is available here.

 

NeuroMat

The Research, Innovation and Dissemination Center for Neuromathematics is hosted by the University of São Paulo and funded by FAPESP (São Paulo Research Foundation).

 

User login

 

Contact

Address:
1010 Matão Street - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. See map.

Phone:
55 11 3091-1717

General contact email:
neuromat@numec.prp.usp.br

Media inquiries email:
comunicacao@numec.prp.usp.br