ALGEBRAIC COMBINATORICS

no. 3
A Cheeger type inequality in finite Cayley sum graphs
Biswas, Arindam1; Saha, Jyoti Prakash2
1 Department of Mathematics Technion - Israel Institute of Technology Haifa 32000, Israel
2 Department of Mathematics Indian Institute of Science Education and Research Bhopal Bhopal Bypass Road, Bhauri, Bhopal 462066, Madhya Pradesh, India
Algebraic Combinatorics, Volume 4 (2021) no. 3, pp. 517-531.

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 + h Σ (G) 4 η , 1 - h Σ (G) 2 2d 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.166
Classification: 05C25, 05C50, 05C75
Keywords: Expander graphs, Cheeger inequality, Spectra of Cayley sum graphs.
Biswas, Arindam 1; Saha, Jyoti Prakash 2

1 Department of Mathematics Technion - Israel Institute of Technology Haifa 32000, Israel
2 Department of Mathematics Indian Institute of Science Education and Research Bhopal Bhopal Bypass Road, Bhauri, Bhopal 462066, Madhya Pradesh, India
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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 = {https://alco.centre-mersenne.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  - https://alco.centre-mersenne.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 https://alco.centre-mersenne.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, Volume 4 (2021) no. 3, pp. 517-531. doi : 10.5802/alco.166. https://alco.centre-mersenne.org/articles/10.5802/alco.166/

[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

Cited by Sources: