Comptes Rendus
Combinatorics
Closed walks and eigenvalues of Abelian Cayley graphs
[Chaînes fermés et valeurs propres des graphes abélien de Cayley]
Comptes Rendus. Mathématique, Volume 342 (2006) no. 9, pp. 635-638.

Soit k3, pour chaque ϵ>0, il existe une constante positive C=C(ϵ,k)>0 telle que pour chaque groupe abélien G et pour chaque sous-ensemble symétrique SG ne contenant pas 1, le nombre de valeurs propres λi de graphe de Cayley X=X(G,S) qui satisfont λikϵ est au moins C|G|.

We show that Abelian Cayley graphs contain many closed walks of even length. This implies that given k3, for each ϵ>0, there exists C=C(ϵ,k)>0 such that for each Abelian group G and each symmetric subset S of G with 1S, the number of eigenvalues λi of the Cayley graph X=X(G,S) such that λikϵ is at least C|G|. This can be regarded as an analogue for Abelian Cayley graphs of a theorem of Serre for regular graphs.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2006.03.005

Sebastian M. Cioabă 1

1 Department of Mathematics, Queen's University at Kingston, Ontario K7L 3N6, Canada
@article{CRMATH_2006__342_9_635_0,
     author = {Sebastian M. Cioab\u{a}},
     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},
}
TY  - JOUR
AU  - Sebastian M. Cioabă
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
DO  - 10.1016/j.crma.2006.03.005
LA  - en
ID  - CRMATH_2006__342_9_635_0
ER  - 
%0 Journal Article
%A Sebastian M. Cioabă
%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
%R 10.1016/j.crma.2006.03.005
%G en
%F CRMATH_2006__342_9_635_0
Sebastian M. Cioabă. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2006.03.005/

[1] N. Alon; Y. Roichman 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] G. Davidoff; P. Sarnak; A. Vallete Elementary Number Theory, Group Theory and Ramanujan Graphs, Cambridge University Press, 2003

[5] U. Fixman Sums of multinomial coefficients, Canad. Math. Bull., Volume 31 (1988) no. 2, pp. 187-189

[6] J. Friedman; R. Murty; J.P. Tillich Spectral estimates of Abelian Cayley graphs, Journal of Combinatorial Theory, Series B, Volume 96 (2006) no. 1, pp. 111-121

[7] A. Lubotzky; R. Phillips; P. Sarnak Ramanujan graphs, Combinatorica, Volume 8 (1988) no. 3, pp. 261-277

[8] A. Nilli Tight estimates for eigenvalues of regular graphs, Electron. J. Combin., Volume 11 (2004) no. 9, pp. 1-4

[9] W.-C. Winnie Li Character sums and Abelian Ramanujan graphs, J. Number Theory, Volume 41 (1992), pp. 199-217

Cité par Sources :

Commentaires - Politique