Discrepancy and eigenvalues of Cayley graphs

Link:
Autor/in:
Erscheinungsjahr:
2016
Medientyp:
Text
Schlagworte:
  • Testing
  • Algorithms
  • Regularity lemma
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Testing
  • Algorithms
  • Regularity lemma
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/2507dcac-12aa-4b85-bd67-4defbac20f3a