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
[Chaînes fermés et valeurs propres des graphes abélien de Cayley]

Présenté par : 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.

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 :

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},
     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/

Bibliographie
Cité par

[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

Xiaogang Liu; Sanming Zhou Eigenvalues of Cayley graphs, The Electronic Journal of Combinatorics, Volume 29 (2022) no. 2, p. research | Zbl:1492.05093
Kashyap Rajeevsarathy; Siddhartha Sarkar; Sivaramakrishnan Lakshmivarahan; Pawan Kumar Aurora Spectral properties of Cayley graphs of split metacyclic groups, Journal of the Ramanujan Mathematical Society, Volume 35 (2020) no. 2, pp. 159-175 | Zbl:7268671
Samar Abbas; Juvaria Tariq; Arif Zaman; Imdadullah Khan, 2017 IEEE 37th International Conference on Distributed Computing Systems Workshops (ICDCSW) (2017), p. 175 | DOI:10.1109/icdcsw.2017.71
Adrian W. Dudek On the spectrum of the generalised Petersen graphs, Graphs and Combinatorics, Volume 32 (2016) no. 5, pp. 1843-1850 | DOI:10.1007/s00373-016-1676-0 | Zbl:1351.05141
Sebastian M. Cioabă; Wiseley Wong The spectrum and toughness of regular graphs, Discrete Applied Mathematics, Volume 176 (2014), pp. 43-52 | DOI:10.1016/j.dam.2013.12.004 | Zbl:1298.05200
Cryptography, Handbook of Finite Fields (2013), p. 777 | DOI:10.1201/b15006-22
Mike Krebs; Natalie Martinez The Combinatorial Trace Method in Action, The College Mathematics Journal, Volume 44 (2013) no. 1, p. 32 | DOI:10.4169/college.math.j.44.1.032
Ka Hin Leung; Vinh Nguyen; Wasin So Nonexistence of a circulant expander family, Bulletin of the Australian Mathematical Society, Volume 83 (2011) no. 1, pp. 87-95 | DOI:10.1017/s0004972710001644 | Zbl:1213.05170
Sebastian M. Cioabă; David A. Gregory; Willem H. Haemers Matchings in regular graphs from eigenvalues, Journal of Combinatorial Theory. Series B, Volume 99 (2009) no. 2, pp. 287-297 | DOI:10.1016/j.jctb.2008.06.008 | Zbl:1205.05177

Cité par 9 documents. Sources : Crossref, zbMATH

Commentaires - Politique