Mathias Schacht
Emory University
Quinta-feira, 22 de janeiro de 2004, 14:00
Sala de Conferências Antonio Gilioli, IME-USP
Resumo:
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 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, while in general the answer is negative.
This is joint work with Yoshiharu Kohayakwa (USP) and Vojtech Rodl (Emory).