For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree.
Revised:
Accepted:
Published online:
Keywords: Spectral gap, diameter, vertex-transitive graphs, discrete Cheeger–Buser inequality
Biswas, Arindam 1; Saha, Jyoti Prakash 2
CC-BY 4.0
@article{ALCO_2023__6_3_689_0,
author = {Biswas, Arindam and Saha, Jyoti Prakash},
title = {A spectral bound for vertex-transitive graphs and their spanning subgraphs},
journal = {Algebraic Combinatorics},
pages = {689--706},
publisher = {The Combinatorics Consortium},
volume = {6},
number = {3},
year = {2023},
doi = {10.5802/alco.278},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.278/}
}
TY - JOUR AU - Biswas, Arindam AU - Saha, Jyoti Prakash TI - A spectral bound for vertex-transitive graphs and their spanning subgraphs JO - Algebraic Combinatorics PY - 2023 SP - 689 EP - 706 VL - 6 IS - 3 PB - The Combinatorics Consortium UR - https://alco.centre-mersenne.org/articles/10.5802/alco.278/ DO - 10.5802/alco.278 LA - en ID - ALCO_2023__6_3_689_0 ER -
%0 Journal Article %A Biswas, Arindam %A Saha, Jyoti Prakash %T A spectral bound for vertex-transitive graphs and their spanning subgraphs %J Algebraic Combinatorics %D 2023 %P 689-706 %V 6 %N 3 %I The Combinatorics Consortium %U https://alco.centre-mersenne.org/articles/10.5802/alco.278/ %R 10.5802/alco.278 %G en %F ALCO_2023__6_3_689_0
Biswas, Arindam; Saha, Jyoti Prakash. A spectral bound for vertex-transitive graphs and their spanning subgraphs. Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 689-706. doi : 10.5802/alco.278. https://alco.centre-mersenne.org/articles/10.5802/alco.278/
[1] On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing, Probab. Engrg. Inform. Sci., Volume 1 (1987) no. 1, pp. 33-46 | DOI | Zbl
[2] Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | DOI | MR
[3] isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR | Zbl
[4] Bipartite subgraphs and the smallest eigenvalue, Combin. Probab. Comput., Volume 9 (2000) no. 1, pp. 1-12 | DOI | MR | Zbl
[5] Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing (STOC ’91), Association for Computing Machinery, 1991, pp. 164-174 | DOI
[6] On a Cheeger type inequality in Cayley graphs of finite groups, European J. Combin., Volume 81 (2019), pp. 298-308 | DOI | MR | Zbl
[7] A Cheeger type inequality in finite Cayley sum graphs, Algebr. Comb., Volume 4 (2021) no. 3, pp. 517-531 | Numdam | MR | Zbl
[8] Expansion in Cayley graphs, Cayley sum graphs and their twists, 2021 | arXiv
[9] Spectra of twists of Cayley and Cayley sum graphs, Adv. in Appl. Math., Volume 132 (2022), Paper no. 102272, 34 pages | MR | Zbl
[10] Expansion in finite simple groups of Lie type, J. Eur. Math. Soc. (JEMS), Volume 17 (2015) no. 6, pp. 1367-1434 | DOI | MR | Zbl
[11] Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages
[12] Cubic Ramanujan graphs, Combinatorica, Volume 12 (1992) no. 3, pp. 275-285 | DOI | MR | Zbl
[13] Spectral graph theory, CBMS Regional Conference Series in Mathematics, 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997, xii+207 pages
[14] The spectral radius and the maximum degree of irregular graphs, Electron. J. Combin., Volume 14 (2007) no. 1, Paper no. 38, 10 pages | MR | Zbl
[15] Extreme eigenvalues of nonregular graphs, J. Combin. Theory Ser. B, Volume 97 (2007) no. 3, pp. 483-486 | DOI | MR | Zbl
[16] Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc., Volume 284 (1984) no. 2, pp. 787-794 | DOI | MR | Zbl
[17] A note on spectral radius and maximum degree of irregular graphs, Graphs Combin., Volume 37 (2021) no. 3, pp. 1121-1127 | DOI | MR | Zbl
[18] 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., Moscow, 1973, pp. 175-183 | Zbl
[19] Fractional decompositions and the smallest-eigenvalue separation, Electron. J. Combin., Volume 26 (2019) no. 4, Paper no. 4.41, 6 pages | MR | Zbl
[20] On the largest eigenvalue of non-regular graphs, J. Combin. Theory Ser. B, Volume 97 (2007) no. 6, pp. 1010-1018 | MR | Zbl
[21] Ramanujan graphs, Combinatorica, Volume 8 (1988) no. 3, pp. 261-277 | DOI | MR | Zbl
[22] Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii, Volume 24 (1988) no. 1, pp. 51-60
[23] Generalized Cayley graphs, Discrete Math., Volume 102 (1992) no. 3, pp. 279-285 | DOI | MR | Zbl
[24] On the bipartiteness constant and expansion of Cayley graphs, European J. Combin., Volume 102 (2022), p. Paper No. 103481 | DOI | MR | Zbl
[25] Existence and explicit constructions of regular Ramanujan graphs for every prime power , J. Combin. Theory Ser. B, Volume 62 (1994) no. 1, pp. 44-62 | DOI | MR | Zbl
[26] Non-bipartite distance-regular graphs with a small smallest eigenvalue, Electron. J. Combin., Volume 26 (2019) no. 2, Paper no. 2.41, 10 pages | MR | Zbl
[27] Lectures on finite Markov chains, Lectures on probability theory and statistics (Saint-Flour, 1996) (Lecture Notes in Math.), Volume 1665, Springer, Berlin, 1997, pp. 301-413 | DOI | MR | Zbl
[28] On the Spectral Gap and the Diameter of Cayley Graphs, Tr. Mat. Inst. Steklova, Volume 314 (2021), pp. 318-337 | MR
[29] The largest eigenvalue of nonregular graphs, J. Combin. Theory Ser. B, Volume 91 (2004) no. 1, pp. 143-146 | DOI | MR | Zbl
[30] A course in combinatorics, Cambridge University Press, Cambridge, 2001, xiv+602 pages
[31] A new result on spectral radius and maximum degree of irregular graphs, Graphs Combin., Volume 37 (2021) no. 3, pp. 1103-1119 | DOI | MR | Zbl
[32] Eigenvectors and eigenvalues of non-regular graphs, Linear Algebra Appl., Volume 409 (2005), pp. 79-86 | DOI | MR | Zbl
Cited by Sources: