{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T04:02:04Z","timestamp":1773115324993,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T00:00:00Z","timestamp":1743638400000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"Abstract<\/jats:title>\n Jord\u00e1n and Tanigawa recently introduced the d<\/jats:italic>-dimensional algebraic connectivity \n \n $$a_d(G)$$<\/jats:tex-math>\n \n \n \n a<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of a graph G<\/jats:italic>. This is a quantitative measure of the d<\/jats:italic>-dimensional rigidity of G<\/jats:italic> which generalizes the well-studied notion of spectral expansion of graphs. We present a new lower bound for \n \n $$a_d(G)$$<\/jats:tex-math>\n \n \n \n a<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> defined in terms of the spectral expansion of certain subgraphs of G<\/jats:italic> associated with a partition of its vertices into d<\/jats:italic> parts. In particular, we obtain a new sufficient condition for the rigidity of a graph G<\/jats:italic>. As a first application, we prove the existence of an infinite family of k<\/jats:italic>-regular d<\/jats:italic>-rigidity-expander graphs for every \n \n $$d\\ge 2$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$k\\ge 2d+1$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Conjecturally, no such family of 2d<\/jats:italic>-regular graphs exists. Second, we show that \n \n $$a_d(K_n)\\ge \\frac{1}{2}\\left\\lfloor \\frac{n}{d}\\right\\rfloor $$<\/jats:tex-math>\n \n \n \n a<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n \n \n n<\/mml:mi>\n d<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, which we conjecture to be essentially tight. In addition, we study the extremal values \n \n $$a_d(G)$$<\/jats:tex-math>\n \n \n \n a<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> attains if G<\/jats:italic> is a minimally d<\/jats:italic>-rigid graph.<\/jats:p>","DOI":"10.1007\/s00493-025-00149-z","type":"journal-article","created":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T07:30:46Z","timestamp":1743838246000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Rigidity Expander Graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"Alan","family":"Lew","sequence":"first","affiliation":[]},{"given":"Eran","family":"Nevo","sequence":"additional","affiliation":[]},{"given":"Yuval","family":"Peled","sequence":"additional","affiliation":[]},{"given":"Orit E.","family":"Raz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,3]]},"reference":[{"key":"149_CR1","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1090\/S0002-9947-1978-0511410-9","volume":"245","author":"L Asimow","year":"1978","unstructured":"Asimow, L., Roth, B.: The rigidity of graphs. Trans. Am. Math. Soc. 245, 279\u2013289 (1978)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"149_CR2","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1017\/S0963548321000249","volume":"31","author":"G Brito","year":"2022","unstructured":"Brito, G., Dumitriu, I., Harris, K.D.: Spectral gap in random bipartite biregular graphs and applications. Combin. Probab. Comput. 31(2), 229\u2013267 (2022)","journal-title":"Combin. Probab. Comput."},{"key":"149_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1939-6","volume-title":"Spectra of graphs. Universitext","author":"AE Brouwer","year":"2012","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of graphs. Universitext. Springer, New York (2012)"},{"issue":"3","key":"149_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF01285816","volume":"12","author":"P Chiu","year":"1992","unstructured":"Chiu, P.: Cubic Ramanujan graphs. Combinatorica 12(3), 275\u2013285 (1992)","journal-title":"Combinatorica"},{"key":"149_CR5","doi-asserted-by":"crossref","unstructured":"Connelly, R.: Rigidity. In: Handbook of Convex Geometry, pp. 223\u2013271. North-Holland, Amsterdam (1993)","DOI":"10.1016\/B978-0-444-89596-7.50012-2"},{"key":"149_CR6","unstructured":"Crapo, H.: On the generic rigidity of plane frameworks. INRIA (Report 1278) (1990)"},{"issue":"98","key":"149_CR7","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler, M.: Algebraic connectivity of graphs. Czechoslov. Math. J. 23(98), 298\u2013305 (1973)","journal-title":"Czechoslov. Math. J."},{"key":"149_CR8","doi-asserted-by":"crossref","unstructured":"Friedman, J.: A proof of Alon\u2019s second eigenvalue conjecture and related problems. Mem. Am. Math. Soc. 195(910), viii+100 (2008)","DOI":"10.1090\/memo\/0910"},{"issue":"3","key":"149_CR9","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22(3), 407\u2013420 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"149_CR10","doi-asserted-by":"crossref","unstructured":"Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. Graduate Studies in Mathematics, vol. 2. American Mathematical Society, Providence (1993)","DOI":"10.1090\/gsm\/002"},{"key":"149_CR11","doi-asserted-by":"crossref","unstructured":"Gray, R.\u00a0M.: Toeplitz and circulant matrices: a review. Found. Trends\u00ae Commun. Inform. Theory 2(3):155\u2013239 (2006)","DOI":"10.1561\/0100000006"},{"issue":"2","key":"149_CR12","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/0611016","volume":"11","author":"R Grone","year":"1990","unstructured":"Grone, R., Merris, R., Sunder, V.S.: The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11(2), 218\u2013238 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"276","key":"149_CR13","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0024-3795(97)10015-5","volume":"275","author":"NJ Higham","year":"1998","unstructured":"Higham, N.J., Cheng, S.H.: Modifying the inertia of matrices arising in optimization. Linear Algebra Appl. 275(276), 261\u2013279 (1998)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"149_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"issue":"3","key":"149_CR15","doi-asserted-by":"publisher","first-page":"2367","DOI":"10.1137\/20M1349849","volume":"36","author":"T Jord\u00e1n","year":"2022","unstructured":"Jord\u00e1n, T., Tanigawa, S.: Rigidity of random subgraphs and eigenvalues of stiffness matrices. SIAM J. Discrete Math. 36(3), 2367\u20132392 (2022)","journal-title":"SIAM J. Discrete Math."},{"key":"149_CR16","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.laa.2014.12.023","volume":"471","author":"T Kolokolnikov","year":"2015","unstructured":"Kolokolnikov, T.: Maximizing algebraic connectivity for certain families of graphs. Linear Algebra Appl. 471, 122\u2013140 (2015)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"149_CR17","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s11856-023-2519-3","volume":"256","author":"A Lew","year":"2023","unstructured":"Lew, A., Nevo, E., Peled, Y., Raz, O.E.: On the $$d$$-dimensional algebraic connectivity of graphs. Israel J. Math. 256(2), 479\u2013511 (2023)","journal-title":"Israel J. Math."},{"key":"149_CR18","unstructured":"Lindemann, T.: Combinatorial aspects of spatial frameworks. PhD thesis, Universit\u00e4t Bremen, (2022)"},{"key":"149_CR19","doi-asserted-by":"crossref","unstructured":"Lubotzky, A.: Expander graphs in pure and applied mathematics. Bull. Amer. Math. Soc. (N.S.) 49(1):113\u2013162 (2012)","DOI":"10.1090\/S0273-0979-2011-01359-3"},{"issue":"3","key":"149_CR20","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"149_CR21","doi-asserted-by":"crossref","unstructured":"Marcus, A.\u00a0W., Spielman, D.\u00a0A., Srivastava, N.: Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2) 182(1):307\u2013325 (2015)","DOI":"10.4007\/annals.2015.182.1.7"},{"issue":"2","key":"149_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1080\/03081088708817827","volume":"22","author":"R Merris","year":"1987","unstructured":"Merris, R.: Characteristic vertices of trees. Linear Multilin. Algebra 22(2), 115\u2013131 (1987)","journal-title":"Linear Multilin. Algebra"},{"key":"149_CR23","unstructured":"Presenza, J.\u00a0F., Mas, I., Giribet, J.\u00a0I., Alvarez-Hamelin, J.\u00a0I.: A new upper bound for the $$d$$-dimensional algebraic connectivity of arbitrary graphs. Preprint at arXiv:2209.14893 (2022)"},{"key":"149_CR24","doi-asserted-by":"crossref","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 3\u201313. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892006"},{"key":"149_CR25","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.amc.2016.04.033","volume":"286","author":"P Xie","year":"2016","unstructured":"Xie, P., Zhang, Z., Comellas, F.: The normalized Laplacian spectrum of subdivisions of a graph. Appl. Math. Comput. 286, 250\u2013256 (2016)","journal-title":"Appl. Math. Comput."},{"key":"149_CR26","unstructured":"Zhu, G.: Quantitative analysis of multi-agent formations: Theory and applications. PhD thesis, Purdue University (2013)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00149-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00149-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00149-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:00:54Z","timestamp":1746522054000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00149-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00149-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"27 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"24"}}