Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below

Jiang, Zilin  ; Polyanskii, Alexandr 

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e163

Résumé

The smallest eigenvalue of a graph is the smallest eigenvalue of its adjacency matrix. We show that the family of graphs with smallest eigenvalue at least $-\lambda $ can be defined by a finite set of forbidden induced subgraphs if and only if $\lambda < \lambda ^*$, where $\lambda ^* = \rho ^{1/2} + \rho ^{-1/2} \approx 2.01980$, and $\rho $ is the unique real root of $x^3 = x + 1$. This resolves a question raised by Bussemaker and Neumaier. As a byproduct, we find all the limit points of smallest eigenvalues of graphs, supplementing Hoffman’s work on those limit points in $[-2, \infty )$.We also prove that the same conclusion about forbidden subgraph characterization holds for signed graphs. Our impetus for the study of signed graphs is to determine the maximum cardinality of a spherical two-distance set with two fixed angles (one acute and one obtuse) in high dimensions. Denote by $N_{\alpha , \beta }(d)$ the maximum number of unit vectors in $\mathbb {R}^d$ where all pairwise inner products lie in $\{\alpha , \beta \}$ with $-1 \le \beta < 0 \le \alpha < 1$. Very recently Jiang, Tidor, Yao, Zhang, and Zhao determined the limit of $N_{\alpha , \beta }(d)/d$ as $d\to \infty $ when $\alpha + 2\beta < 0$ or $(1-\alpha )/(\alpha -\beta ) \in \{1,\sqrt 2,\sqrt 3\}$, and they proposed a conjecture on the limit in terms of eigenvalue multiplicities of signed graphs. We establish their conjecture whenever $(1-\alpha )/(\alpha - \beta ) < \lambda ^*$.

Détail

DOI : 10.1017/fms.2025.10110

Bibliographie

[1] Acharya, H. and Jiang, Z., ‘Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult’, Preprint, 2024, [math.CO]. Google Scholar | arXiv

[2] Balla, I., Dräxler, F., Keevash, P. and Sudakov, B., ‘Equiangular lines and spherical codes in Euclidean space’, Invent. Math. 211(1) (2018), 179–212, [math.CO].10.1007/s00222-017-0746-0 Google Scholar | arXiv | DOI

[3] Belardo, F., Cioabă, S. M., Koolen, J. and Wang, J., ‘Open problems in the spectral theory of signed graphs’, Art Discrete Appl. Math. 1(2) (2018), Paper No. 2.10, 23, [math.CO]. Google Scholar | arXiv

[4] Brouwer, A. E. and Neumaier, A., ‘The graphs with spectral radius between 2 and ’, Linear Algebra Appl. 114 115 (1989), 273–276.10.1016/0024-3795(89)90466-7 Google Scholar | DOI

[5] Bukh, B., ‘Bounds on equiangular lines and on related spherical codes’, SIAM J. Discrete Math. 30(1) (2016), 549–554, [math.CO].10.1137/15M1036920 Google Scholar | arXiv | DOI

[6] Bussemaker, F. C. and Neumaier, A., ‘Exceptional graphs with smallest eigenvalue –2 and related problems’, Math. Comp. 59(200) (1992), 583–608, with microfiche supplement.10.1090/S0025-5718-1992-1134718-6 Google Scholar | DOI

[7] Cameron, P. J., Goethals, J.-M., Seidel, J. J. and Shult, E. E., ‘Line graphs, root systems, and elliptic geometry’, J. Algebra 43(1) (1976), 305–327.10.1016/0021-8693(76)90162-9 Google Scholar | DOI

[8] Chawathe, P. D. and Vijayakumar, G. R., ‘A characterization of signed graphs represented by root system ’, European J. Combin. 11(6) (1990), 523–533.10.1016/S0195-6698(13)80037-6 Google Scholar | DOI

[9] Cvetković, D., Doob, M. and Gutman, I., ‘On graphs whose spectral radius does not exceed ’, Ars Combin. 14 (1982), 225–239. Google Scholar

[10] Cvetković, D., Doob, M. and Simić, S., ‘Some results on generalized line graphs’, C. R. Math. Rep. Acad. Sci. Canada 2(3) (1980), 147–150. Google Scholar

[11] Cvetković, D., Doob, M. and Simić, S., ‘Generalized line graphs’, J. Graph Theory 5(4) (1981), 385–399.10.1002/jgt.3190050408 Google Scholar | DOI

[12] Cvetković, D., Rowlinson, P. and Simić, S., Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue –2, London Mathematical Society Lecture Note Series, vol. 314 (Cambridge Univ. Press, Cambridge, 2004).10.1017/CBO9780511751752 Google Scholar | DOI

[13] Dickson, L. E., ‘Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors’, Amer. J. Math. 35(4) (1913), 413–422.10.2307/2370405 Google Scholar | DOI

[14] Doob, M., ‘The limit points of eigenvalues of graphs’, Linear Algebra Appl. 114 115 (1989), 659–662.10.1016/0024-3795(89)90485-0 Google Scholar | DOI

[15] Greaves, G., Koolen, J., Munemasa, A., Sano, Y. and Taniguchi, T., ‘Edge-signed graphs with smallest eigenvalue greater than –2’, J. Combin. Theory Ser. B 110 (2015), 90–111, [math.CO].10.1016/j.jctb.2014.07.006 Google Scholar | arXiv | DOI

[16] Hoffman, A. J., ‘On limit points of spectral radii of non-negative symmetric integral matrices’, in Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Mathematics, vol. 303 (Springer, 1972), 165–172.10.1007/BFb0067367 Google Scholar | DOI

[17] Hoffman, A. J., ‘On graphs whose least eigenvalue exceeds ’, Linear Algebra Appl. 16(2) (1977), 153–165.10.1016/0024-3795(77)90027-1 Google Scholar | DOI

[18] Hoffman, A. J., ‘On limit points of the least eigenvalue of a graph’, Ars Combin. 3 (1977), 3–14. Google Scholar

[19] Jiang, Z., ‘On symmetric hollow integer matrices with eigenvalues bounded from below’, Linear Algebra Appl. 709 (2025), 233–240. [math.CO].10.1016/j.laa.2025.01.021 Google Scholar | arXiv | DOI

[20] Jiang, Z. and Polyanskii, A., ‘Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines’, Israel J. Math. 236(1) (2020), 393–421, [math.CO].10.1007/s11856-020-1983-2 Google Scholar | arXiv | DOI

[21] Jiang, Z., Tidor, J., Yao, Y., Zhang, S. and Zhao, Y., ‘Equiangular lines with a fixed angle’, Ann. Math. (2) 194(3) (2021), 729–743, [math.CO].10.4007/annals.2021.194.3.3 Google Scholar | arXiv | DOI

[22] Jiang, Z., Tidor, J., Yao, Y., Zhang, S. and Zhao, Y., ‘Spherical two-distance sets and eigenvalues of signed graphs’, Combinatorica 43(2) (2023), 203–232, [math.CO].10.1007/s00493-023-00002-1 Google Scholar | arXiv | DOI

[23] Kumar, V., Rao, S. B. and Singhi, N. M., ‘Graphs with eigenvalues at least –2’, Linear Algebra Appl. 46 (1982), 27–42.10.1016/0024-3795(82)90023-4 Google Scholar | DOI

[24] Mckee, J. and Smyth, C., ‘Integer symmetric matrices having all their eigenvalues in the interval ’, J. Algebra 317(1) (2007), 260–290, [math.CO].10.1016/j.jalgebra.2007.05.019 Google Scholar | arXiv | DOI

[25] Mckee, J. and Smyth, C., ‘Integer symmetric matrices of small spectral radius and small Mahler measure’, Int. Math. Res. Not. IMRN 2012(1) (2012), 102–136, [math.NT].10.1093/imrn/rnr011 Google Scholar | arXiv | DOI

[26] Rao, S. B., Singhi, N. M. and Vijayan, K. S., ‘The minimal forbidden subgraphs for generalized line-graphs’, in Combinatorics and Graph Theory (Calcutta, 1980), Lecture Notes in Mathematics, vol. 885 (Springer, Berlin-New York, 1981), 459–472.10.1007/BFb0092290 Google Scholar | DOI

[27] Van Rooij, A. C. M. and Wilf, H. S., ‘The interchange graph of a finite graph’, Acta Math. Acad. Sci. Hungar. 16 (1965), 263–269.10.1007/BF01904834 Google Scholar | DOI

[28] Shearer, J. B., ‘On the distribution of the maximum eigenvalue of graphs’, Linear Algebra Appl. 114 115 (1989), 17–20.10.1016/0024-3795(89)90449-7 Google Scholar | DOI

[29] Smith, J. H., ‘Some properties of the spectrum of a graph’, in Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, New York (1970), 403–406. Google Scholar

[30] Stanić, Z., ‘Notes on exceptional signed graphs’, Ars Math. Contemp. 18(1) (2020), 105–115.10.26493/1855-3974.1933.2df Google Scholar | DOI

[31] Vijayakumar, G. R., ‘Signed graphs represented by D∞’, European J. Combin. 8(1) (1987), 103–112.10.1016/S0195-6698(87)80024-0 Google Scholar | DOI

[32] Wang, D., Dong, W., Hou, Y. and Li, D., ‘On signed graphs whose spectral radius does not exceed ’, Discrete Math. 346(6) (2023), 113358, [math.CO]. Google Scholar | arXiv

[33] Witt, E., ‘Spiegelungsgruppen und Aufzählung halbeinfacher Liescher Ringe’, Abh. Math. Sem. Hansischen Univ. 14 (1941), 289–322.10.1007/BF02940749 Google Scholar | DOI

[34] Zaslavsky, T., ‘Matrices in the theory of signed simple graphs’, in Advances in Discrete Mathematics and Applications: Mysore, 2008, Ramanujan Mathematical Society Lecture Notes Series, vol. 13 (Ramanujan Math. Soc., Mysore, 2010), 207–229, [math.CO]. Google Scholar | arXiv