Discrepancy and eigenvalues of Cayley graphs

详细信息    查看全文

• 作者：Yoshiharu Kohayakawa ; Vojtěch Rödl ; Mathias Schacht
• 关键词：eigenvalue ; discrepancy ; quasirandomness ; Cayley graph
• 刊名：Czechoslovak Mathematical Journal
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：66
• 期：3
• 页码：941-954
• 全文大小：191 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Analysis
  Convex and Discrete Geometry
  Ordinary Differential Equations
  Mathematical Modeling and IndustrialMathematics
  
• 出版者：Springer Netherlands
• ISSN：1572-9141
• 卷排序：66

文摘

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.