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

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

Article information
Cite this article

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

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

@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

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