We show that Abelian Cayley graphs contain many closed walks of even length. This implies that given , for each , there exists such that for each Abelian group G and each symmetric subset S of G with , the number of eigenvalues of the Cayley graph such that is at least . This can be regarded as an analogue for Abelian Cayley graphs of a theorem of Serre for regular graphs.
Soit , pour chaque , il existe une constante positive telle que pour chaque groupe abélien G et pour chaque sous-ensemble symétrique ne contenant pas 1, le nombre de valeurs propres de graphe de Cayley qui satisfont est au moins .
Accepted:
Published online:
@article{CRMATH_2006__342_9_635_0, author = {Cioab\u{a}, Sebastian M.}, title = {Closed walks and eigenvalues of {Abelian} {Cayley} graphs}, journal = {Comptes Rendus. Math\'ematique}, pages = {635--638}, publisher = {Elsevier}, volume = {342}, number = {9}, year = {2006}, doi = {10.1016/j.crma.2006.03.005}, language = {en}, url = {http://archive.numdam.org/articles/10.1016/j.crma.2006.03.005/} }
TY - JOUR AU - Cioabă, Sebastian M. TI - Closed walks and eigenvalues of Abelian Cayley graphs JO - Comptes Rendus. Mathématique PY - 2006 SP - 635 EP - 638 VL - 342 IS - 9 PB - Elsevier UR - http://archive.numdam.org/articles/10.1016/j.crma.2006.03.005/ DO - 10.1016/j.crma.2006.03.005 LA - en ID - CRMATH_2006__342_9_635_0 ER -
%0 Journal Article %A Cioabă, Sebastian M. %T Closed walks and eigenvalues of Abelian Cayley graphs %J Comptes Rendus. Mathématique %D 2006 %P 635-638 %V 342 %N 9 %I Elsevier %U http://archive.numdam.org/articles/10.1016/j.crma.2006.03.005/ %R 10.1016/j.crma.2006.03.005 %G en %F CRMATH_2006__342_9_635_0
Cioabă, Sebastian M. Closed walks and eigenvalues of Abelian Cayley graphs. Comptes Rendus. Mathématique, Volume 342 (2006) no. 9, pp. 635-638. doi : 10.1016/j.crma.2006.03.005. http://archive.numdam.org/articles/10.1016/j.crma.2006.03.005/
[1] Random Cayley graphs and expanders, Random Structures Algorithms, Volume 5 (1994) no. 2, pp. 271-284
[2] S.M. Cioabă, Eigenvalues, expanders and gaps between primes, Ph.D. Thesis, Queen's University at Kingston, Canada, 2005
[3] S.M. Cioabă, On the extreme eigenvalues of regular graphs, Journal of Combinatorial Theory, Series B, in press
[4] Elementary Number Theory, Group Theory and Ramanujan Graphs, Cambridge University Press, 2003
[5] Sums of multinomial coefficients, Canad. Math. Bull., Volume 31 (1988) no. 2, pp. 187-189
[6] Spectral estimates of Abelian Cayley graphs, Journal of Combinatorial Theory, Series B, Volume 96 (2006) no. 1, pp. 111-121
[7] Ramanujan graphs, Combinatorica, Volume 8 (1988) no. 3, pp. 261-277
[8] Tight estimates for eigenvalues of regular graphs, Electron. J. Combin., Volume 11 (2004) no. 9, pp. 1-4
[9] Character sums and Abelian Ramanujan graphs, J. Number Theory, Volume 41 (1992), pp. 199-217
Cited by Sources: