# ALGEBRAIC COMBINATORICS

A Cheeger type inequality in finite Cayley sum graphs
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}_{\Sigma }\left(G,S\right)$ is undirected and connected. We show that the non-trivial spectrum of the normalised adjacency operator of ${C}_{\Sigma }\left(G,S\right)$ 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 $\left(-1+\frac{{h}_{\Sigma }{\left(G\right)}^{4}}{\eta },1-\frac{{h}_{\Sigma }{\left(G\right)}^{2}}{2{d}^{2}}\right]$, where ${h}_{\Sigma }\left(G\right)$ denotes the vertex Cheeger constant of the $d$-regular graph ${C}_{\Sigma }\left(G,S\right)$ and $\eta ={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.

Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.166
Classification: 05C25,  05C50,  05C75
Keywords: Expander graphs, Cheeger inequality, Spectra of Cayley sum graphs.
@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/}
}
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) | Article | MR 875835 | Zbl 0661.05053

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

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

[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 | Article | MR 3353804 | Zbl 1331.20060

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

[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 0402831 | Zbl 0212.44903

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

[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 1395858 | Zbl 0864.05070

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

[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 0435006

[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 | Article | MR 2141661 | Zbl 1110.11009

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

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

[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 | Article | MR 2467826 | Zbl 1202.05078

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

[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) | Article | MR 1308046 | Zbl 0826.22012

[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 | Article | MR 4110517 | Zbl 1448.05153

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