Let $G$ be a finite group with $\left|G\right|\u2a7e4$ and $S$ be a subset of $G$ with $\left|S\right|=d$ such that the Cayley sum graph ${C}_{\Sigma}(G,S)$ is undirected and connected. We show that the non-trivial spectrum of the normalised adjacency operator of ${C}_{\Sigma}(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 $\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}(G,S)$ 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:

Keywords: Expander graphs, Cheeger inequality, Spectra of Cayley sum graphs.

^{1}; Saha, Jyoti Prakash

^{2}

@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 -

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. http://www.numdam.org/articles/10.5802/alco.166/

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

[2] ${\lambda}_{1},$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR

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

[4] 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] 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] 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] Diameters and eigenvalues, J. Amer. Math. Soc., Volume 2 (1989) no. 2, pp. 187-196 | DOI | MR | Zbl

[8] 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] 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] 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] 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] On the chromatic number of random Cayley graphs, Combin. Probab. Comput., Volume 26 (2017) no. 2, pp. 248-266 | DOI | MR | Zbl

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

[14] Connectivity of addition Cayley graphs, J. Combin. Theory Ser. B, Volume 99 (2009) no. 1, pp. 202-217 | DOI | MR | Zbl

[15] On subgraphs of random Cayley sum graphs, European J. Combin., Volume 70 (2018), pp. 61-74 | DOI | MR | Zbl

[16] 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] Subgroup perfect codes in Cayley sum graphs, Des. Codes Cryptogr., Volume 88 (2020) no. 7, pp. 1447-1461 | DOI | MR | Zbl

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

*Cited by Sources: *