Closed walks and eigenvalues of Abelian Cayley graphs

Cioabă, Sebastian M.

doi:10.1016/j.crma.2006.03.005

Combinatorics

Closed walks and eigenvalues of Abelian Cayley graphs
[Chaînes fermés et valeurs propres des graphes abélien de Cayley]

Présenté par : Jean-Pierre Serre

Cioabă, Sebastian M.¹

¹ Department of Mathematics, Queen's University at Kingston, Ontario K7L 3N6, Canada

Comptes Rendus. Mathématique, Tome 342 (2006) no. 9, pp. 635-638.

Résumé
Abstract

Soit $k ⩾ 3$ , 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 $S \subset G$ ne contenant pas 1, le nombre de valeurs propres $λ_{i}$ de graphe de Cayley $X = X (G, S)$ qui satisfont $λ_{i} ⩾ k - ϵ$ est au moins $C \cdot | G |$ .

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

Reçu le : 2005-06-14
Accepté le : 2006-02-23
Publié le : 2006-03-29

DOI : 10.1016/j.crma.2006.03.005

Affiliations des auteurs :

Cioabă, Sebastian M. ¹

¹ Department of Mathematics, Queen's University at Kingston, Ontario K7L 3N6, Canada

@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://www.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://www.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://www.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, Tome 342 (2006) no. 9, pp. 635-638. doi : 10.1016/j.crma.2006.03.005. http://www.numdam.org/articles/10.1016/j.crma.2006.03.005/

Bibliographie
Cité par

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

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

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

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

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

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

Cité par Sources :