Closed walks and eigenvalues of Abelian Cayley graphs

Sebastian M. Cioabă

doi:10.1016/j.crma.2006.03.005

Combinatorics

Closed walks and eigenvalues of Abelian Cayley graphs

Presented by: Jean-Pierre Serre

Sebastian M. Cioabă ¹

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

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

Abstract (Original language)
Résumé

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.

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 |$ .

Received: 2005-06-14
Accepted: 2006-02-23
Published online: 2006-03-29

DOI: 10.1016/j.crma.2006.03.005

Author's affiliations:

Sebastian M. Cioabă ¹

¹ 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},
     year = {2006},
     publisher = {Elsevier},
     volume = {342},
     number = {9},
     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

References
Cited by

[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

Cited by Sources:

Comments - Policy