A Cheeger type inequality in finite Cayley sum graphs

Biswas, Arindam; Saha, Jyoti Prakash

doi:10.5802/alco.166

Biswas, Arindam ¹ ; Saha, Jyoti Prakash ²

¹ Department of Mathematics Technion - Israel Institute of Technology Haifa 32000, Israel
² Department of Mathematics Indian Institute of Science Education and Research Bhopal Bhopal Bypass Road, Bhauri, Bhopal 462066, Madhya Pradesh, India

Algebraic Combinatorics, Tome 4 (2021) no. 3, pp. 517-531.

Résumé

Let $G$ be a finite group with $| G | ⩾ 4$ and $S$ be a subset of $G$ with $| S | = d$ such that the Cayley sum graph $C_{Σ} (G, S)$ is undirected and connected. We show that the non-trivial spectrum of the normalised adjacency operator of $C_{Σ} (G, S)$ is controlled by its Cheeger constant and its degree. We establish an explicit lower bound for the non-trivial spectrum of these graphs, namely, the non-trivial eigenvalues of the normalised adjacency operator lies in the interval $(- 1 + \frac{h_{Σ} {(G)}^{4}}{η}, 1 - \frac{h_{Σ} {(G)}^{2}}{2 d^{2}}]$ , where $h_{Σ} (G)$ denotes the vertex Cheeger constant of the $d$ -regular graph $C_{Σ} (G, S)$ and $η = 2^{9} d^{8}$ . Further, we improve upon a recently obtained bound on the non-trivial spectrum of the normalised adjacency operator of the Cayley graph of finite groups.

Reçu le : 2020-06-05
Révisé le : 2020-12-20
Accepté le : 2020-12-20
Publié le : 2021-06-22

DOI : 10.5802/alco.166

Classification : 05C25, 05C50, 05C75
Mots-clés : Expander graphs, Cheeger inequality, Spectra of Cayley sum graphs.

Affiliations des auteurs :

Biswas, Arindam ¹ ; Saha, Jyoti Prakash ²

@article{ALCO_2021__4_3_517_0,
     author = {Biswas, Arindam and Saha, Jyoti Prakash},
     title = {A {Cheeger} type inequality in finite {Cayley} sum graphs},
     journal = {Algebraic Combinatorics},
     pages = {517--531},
     publisher = {MathOA foundation},
     volume = {4},
     number = {3},
     year = {2021},
     doi = {10.5802/alco.166},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/alco.166/}
}

TY  - JOUR
AU  - Biswas, Arindam
AU  - Saha, Jyoti Prakash
TI  - A Cheeger type inequality in finite Cayley sum graphs
JO  - Algebraic Combinatorics
PY  - 2021
SP  - 517
EP  - 531
VL  - 4
IS  - 3
PB  - MathOA foundation
UR  - http://www.numdam.org/articles/10.5802/alco.166/
DO  - 10.5802/alco.166
LA  - en
ID  - ALCO_2021__4_3_517_0
ER  -

%0 Journal Article
%A Biswas, Arindam
%A Saha, Jyoti Prakash
%T A Cheeger type inequality in finite Cayley sum graphs
%J Algebraic Combinatorics
%D 2021
%P 517-531
%V 4
%N 3
%I MathOA foundation
%U http://www.numdam.org/articles/10.5802/alco.166/
%R 10.5802/alco.166
%G en
%F ALCO_2021__4_3_517_0

Biswas, Arindam; Saha, Jyoti Prakash. A Cheeger type inequality in finite Cayley sum graphs. Algebraic Combinatorics, Tome 4 (2021) no. 3, pp. 517-531. doi : 10.5802/alco.166. http://www.numdam.org/articles/10.5802/alco.166/

Bibliographie
Cité par

[1] Alon, Noga Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | DOI | MR | Zbl

[2] Alon, Noga; Milman, Vitali D. $λ_{1},$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR

[3] Biswas, Arindam On a Cheeger type inequality in Cayley graphs of finite groups, European J. Combin., Volume 81 (2019), pp. 298-308 | DOI | MR | Zbl

[4] Breuillard, Emmanuel; Green, Ben; Guralnick, Robert; Tao, Terence Expansion in finite simple groups of Lie type, J. Eur. Math. Soc. (JEMS), Volume 17 (2015) no. 6, pp. 1367-1434 | DOI | MR | Zbl

[5] Buser, Peter A note on the isoperimetric constant, Ann. Sci. École Norm. Sup. (4), Volume 15 (1982) no. 2, pp. 213-230 | DOI | Numdam | MR | Zbl

[6] Cheeger, Jeff A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969), Princeton University Press, 1970, pp. 195-199 | MR | Zbl

[7] Chung, Fan R. K. Diameters and eigenvalues, J. Amer. Math. Soc., Volume 2 (1989) no. 2, pp. 187-196 | DOI | MR | Zbl

[8] Chung, Fan R. K. Laplacians of graphs and Cheeger’s inequalities, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) (Bolyai Soc. Math. Stud.), Volume 2, János Bolyai Math. Soc., Budapest, 1996, pp. 157-172 | MR | Zbl

[9] DeVos, Matt; Goddyn, Luis; Mohar, Bojan; Šámal, Robert Cayley sum graphs and eigenvalues of $(3, 6)$ -fullerenes, J. Combin. Theory Ser. B, Volume 99 (2009) no. 2, pp. 358-369 | DOI | MR | Zbl

[10] Freĭman, Gregory A. Groups and the inverse problems of additive number theory, Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), Kalinin Gos. Univ., 1973, pp. 175-183 | MR

[11] Green, Ben Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica, Volume 25 (2005) no. 3, pp. 307-326 | DOI | MR | Zbl

[12] Green, Ben On the chromatic number of random Cayley graphs, Combin. Probab. Comput., Volume 26 (2017) no. 2, pp. 248-266 | DOI | MR | Zbl

[13] Green, Ben; Morris, Robert Counting sets with small sumset and applications, Combinatorica, Volume 36 (2016) no. 2, pp. 129-159 | DOI | MR | Zbl

[14] Grynkiewicz, David; Lev, Vsevolod F.; Serra, Oriol Connectivity of addition Cayley graphs, J. Combin. Theory Ser. B, Volume 99 (2009) no. 1, pp. 202-217 | DOI | MR | Zbl

[15] Konyagin, Sergeĭ V.; Shkredov, Ilâya D. On subgraphs of random Cayley sum graphs, European J. Combin., Volume 70 (2018), pp. 61-74 | DOI | MR | Zbl

[16] Lubotzky, Alexander Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, 125, Birkhäuser Verlag, Basel, 1994, xii+195 pages (With an appendix by Jonathan D. Rogawski) | DOI | MR | Zbl

[17] Ma, Xuanlong; Feng, Min; Wang, Kaishun Subgroup perfect codes in Cayley sum graphs, Des. Codes Cryptogr., Volume 88 (2020) no. 7, pp. 1447-1461 | DOI | MR | Zbl

[18] Mrazović, Rudi Extractors in Paley graphs: a random model, European J. Combin., Volume 54 (2016), pp. 154-162 | DOI | MR | Zbl

Cité par Sources :