Discrepancy and eigenvalues of Cayley graphs

被引：5
作者：
Kohayakawa, Yoshiharu [1 ]
Rodl, Vojtch [2 ]
Schacht, Mathias [3 ]
机构：
[1] Univ Sao Paulo, Inst Matemat & Estat, R Matao,1010 Vila Univ, BR-05508090 Sao Paulo, Brazil
[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30307 USA
[3] Univ Hamburg, Fachbereich Math, Bundesstr 55, D-20146 Hamburg, Germany
来源：
CZECHOSLOVAK MATHEMATICAL JOURNAL | 2016年 / 66卷 / 03期
基金：
巴西圣保罗研究基金会; 美国国家科学基金会;
关键词：
eigenvalue; discrepancy; quasirandomness; Cayley graph;
D O I：
10.1007/s10587-016-0302-x
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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.
引用
收藏
页码：941 / 954
页数：14
相关论文
共 29 条
  • [1] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS
    ALON, N
    MILMAN, VD
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) : 73 - 88
  • [2] EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS
    ALON, N
    CHUNG, FRK
    [J]. DISCRETE MATHEMATICS, 1988, 72 (1-3) : 15 - 19
  • [3] Alon N, 2008, WILEY INTERSCIENCE S
  • [4] QUASI-RANDOMNESS AND ALGORITHMIC REGULARITY FOR GRAPHS WITH GENERAL DEGREE DISTRIBUTIONS
    Alon, Noga
    Coja-Oghlan, Amin
    Han, Hiep
    Kang, Mihyun
    Roedl, Vojtech
    Schacht, Mathias
    [J]. SIAM JOURNAL ON COMPUTING, 2010, 39 (06) : 2336 - 2362
  • [5] SPECTRA OF CAYLEY GRAPHS
    BABAI, L
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (02) : 180 - 189
  • [6] Lifts, discrepancy and nearly optimal spectral cap
    Bilu, Yonatan
    Linial, Nathan
    [J]. COMBINATORICA, 2006, 26 (05) : 495 - 519
  • [7] QUASI-RANDOM GRAPHS
    CHUNG, FRK
    GRAHAM, RL
    WILSON, RM
    [J]. COMBINATORICA, 1989, 9 (04) : 345 - 362
  • [8] Conlon D., ARXIV160303025MATHCO
  • [9] Extremal results in sparse pseudorandom graphs
    Conlon, David
    Fox, Jacob
    Zhao, Yufei
    [J]. ADVANCES IN MATHEMATICS, 2014, 256 : 206 - 290
  • [10] Donath W. E., 1972, IBM Technical Disclosure Bulletin, V15, P938
123