{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:05Z","timestamp":1740107105508,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Counting in Sparse Graphs Lend\u00fclet Research Group"},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["747430"],"award-info":[{"award-number":["747430"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EFOP","award":["EFOP-3.6.3-VEKOP-16-2017-00002"],"award-info":[{"award-number":["EFOP-3.6.3-VEKOP-16-2017-00002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2021,11]]},"abstract":"Abstract<\/jats:title>Let F<\/jats:italic>(G<\/jats:italic>) be the number of forests of a graph G<\/jats:italic>. Similarly let C<\/jats:italic>(G<\/jats:italic>) be the number of connected spanning subgraphs of a connected graph G<\/jats:italic>. We bound F<\/jats:italic>(G<\/jats:italic>) and C<\/jats:italic>(G<\/jats:italic>) for regular graphs and for graphs with a fixed average degree. Among many other things we study $$f_d=\\sup _{G\\in {\\mathcal {G}}_d}F(G)^{1\/v(G)}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n \n sup<\/mml:mo>\n \n G<\/mml:mi>\n \u2208<\/mml:mo>\n \n G<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:msub>\n F<\/mml:mi>\n \n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n v<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $${\\mathcal {G}}_d$$<\/jats:tex-math>\n \n G<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the family of d<\/jats:italic>-regular graphs, and v<\/jats:italic>(G<\/jats:italic>) denotes the number of vertices of a graph G<\/jats:italic>. We show that $$f_3=2^{3\/2}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and if $$(G_n)_n$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n G<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a sequence of 3-regular graphs with the length of the shortest cycle tending to infinity, then $$\\lim _{n\\rightarrow \\infty }F(G_n)^{1\/v(G_n)}=2^{3\/2}$$<\/jats:tex-math>\n \n \n lim<\/mml:mo>\n \n n<\/mml:mi>\n \u2192<\/mml:mo>\n \u221e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n F<\/mml:mi>\n \n \n (<\/mml:mo>\n \n G<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n v<\/mml:mi>\n (<\/mml:mo>\n \n G<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also improve on the previous best bounds on $$f_d$$<\/jats:tex-math>\n \n f<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$4\\le d\\le 9$$<\/jats:tex-math>\n \n 4<\/mml:mn>\n \u2264<\/mml:mo>\n d<\/mml:mi>\n \u2264<\/mml:mo>\n 9<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00373-021-02382-x","type":"journal-article","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T09:03:06Z","timestamp":1627635786000},"page":"2655-2678","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Number of Forests and Connected Spanning Subgraphs"],"prefix":"10.1007","volume":"37","author":[{"given":"M\u00e1rton","family":"Borb\u00e9nyi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6909-5253","authenticated-orcid":false,"given":"P\u00e9ter","family":"Csikv\u00e1ri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haoran","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,30]]},"reference":[{"key":"2382_CR1","volume-title":"The Probabilistic Methods","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.: The Probabilistic Methods. Wiley, Hoboken (2016)"},{"key":"2382_CR2","volume-title":"Spectra of Graphs","author":"AE Brouwer","year":"2011","unstructured":"Brouwer, A.E., Haemars, W.: Spectra of Graphs. Springer, Berlin (2011)"},{"issue":"1","key":"2382_CR3","doi-asserted-by":"publisher","first-page":"R4","DOI":"10.37236\/1697","volume":"10","author":"N Calkin","year":"2003","unstructured":"Calkin, N., Merino, C., Noble, S., Noy, M.: Improved bounds for the number of forests and acyclic orientations in the square lattice. Electron. J. Combin. 10(1), R4 (2003)","journal-title":"Electron. J. Combin."},{"key":"2382_CR4","doi-asserted-by":"publisher","first-page":"2050249","DOI":"10.1142\/S0217979220502495","volume":"34","author":"C Chang","year":"2020","unstructured":"Chang, C., Shrock, R.: Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices. Int. J. Mod. Phys. B 34, 2050249 (2020)","journal-title":"Int. J. Mod. Phys. B"},{"key":"2382_CR5","unstructured":"Chang, C., Shrock, R.: Exponential growth constants for spanning forests on Archimedean lattices: values and comparisons of upper bounds. arXiv:2012.13468"},{"issue":"6","key":"2382_CR6","doi-asserted-by":"publisher","first-page":"1811","DOI":"10.4171\/JEMS\/706","volume":"19","author":"P Csikv\u00e1ri","year":"2017","unstructured":"Csikv\u00e1ri, P.: Lower matching conjecture, and a new proof of Schrijvers and Gurvitss theorems. J. Eur. Math. Soc. 19(6), 1811\u20131844 (2017)","journal-title":"J. Eur. Math. Soc."},{"key":"2382_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01651330","volume":"22","author":"CM Fortuin","year":"1971","unstructured":"Fortuin, C.M., Kasteleyn, R.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Commun. Math. Phys. 22, 89\u2013103 (1971)","journal-title":"Commun. Math. Phys."},{"key":"2382_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory, Graduate Texts in Mathematics","author":"C Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.F.: Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207. Springer Science and Business Media, Berlin (2001)"},{"key":"2382_CR9","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20012","volume":"24","author":"GR Grimmett","year":"2004","unstructured":"Grimmett, G.R., Winkler, S.N.: Negative association in uniform forests and connected graphs. Random Struct. Algorithms 24, 444\u2013460 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"2382_CR10","volume-title":"An Exponential Bound for the Probability of Nonexistence of a Specified Subgraph in a Random Graph","author":"S Janson","year":"1988","unstructured":"Janson, S., Luczak, T., Rucinski, A.: An Exponential Bound for the Probability of Nonexistence of a Specified Subgraph in a Random Graph. Institute for Mathematics and its Applications, Berlin (1988)"},{"issue":"3","key":"2382_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF01261322","volume":"16","author":"N Kahale","year":"1996","unstructured":"Kahale, N., Schulman, L.J.: Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph. Combinatorica 16(3), 383\u2013397 (1996)","journal-title":"Combinatorica"},{"key":"2382_CR12","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: \u00dcber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str\u00f6me gefuhrt wird. Ann. Phys. Chem. 72, 497\u2013508 (1847). (English transl. IRE Trans. Circuit Theory CT-5 (1958), 4-7)","journal-title":"Ann. Phys. Chem."},{"issue":"1","key":"2382_CR13","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579176","volume":"1","author":"DJ Kleitman","year":"1981","unstructured":"Kleitman, D.J., Winston, K.J.: Forests and score vectors. Combinatorica 1(1), 49\u201354 (1981)","journal-title":"Combinatorica"},{"issue":"3","key":"2382_CR14","doi-asserted-by":"publisher","first-page":"P44","DOI":"10.37236\/3326","volume":"20","author":"L Kozma","year":"2013","unstructured":"Kozma, L., Moran, S.: Shattering, graph orientations, and connectivity. Electron. J. Combin. 20(3), P44 (2013)","journal-title":"Electron. J. Combin."},{"key":"2382_CR15","unstructured":"Linial, N.: Lifts of graphs, (talk slides), http:\/\/www.cs.huji.ac.il\/~nati\/PAPERS\/lifts_ talk.pdf"},{"issue":"2","key":"2382_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0195-6698(83)80045-6","volume":"4","author":"BD McKay","year":"1983","unstructured":"McKay, B.D.: Spanning trees in regular graphs. Eur. J. Combin. 4(2), 149\u2013160 (1983)","journal-title":"Eur. J. Combin."},{"key":"2382_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0024-3795(81)90150-6","volume":"40","author":"BD McKay","year":"1981","unstructured":"McKay, B.D.: The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40, 203\u2013216 (1981)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"2382_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.jctb.2011.08.003","volume":"102","author":"AP Mani","year":"2012","unstructured":"Mani, A.P.: On some Tutte polynomial sequences in the square lattice. J. Combin. Theory Ser. B 102(2), 436\u2013453 (2012)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2382_CR19","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01608795","volume":"3","author":"C Merino","year":"1999","unstructured":"Merino, C., Welsh, D.J.A.: Forests, colorings and acyclic orientations of the square lattice. Ann. Combin. 3, 417\u2013429 (1999)","journal-title":"Ann. Combin."},{"key":"2382_CR20","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1063\/1.533200","volume":"41","author":"R Pemantle","year":"2000","unstructured":"Pemantle, R.: Towards a theory of negative independence. J. Math. Phys. 41, 1371\u20131390 (2000)","journal-title":"J. Math. Phys."},{"key":"2382_CR21","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0021-9800(68)80087-0","volume":"4","author":"RC Read","year":"1968","unstructured":"Read, R.C.: An introduction to chromatic polynomials. J. Combin. Theory 4, 52\u201371 (1968)","journal-title":"J. Combin. Theory"},{"issue":"2","key":"2382_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"RP Stanley","year":"1973","unstructured":"Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5(2), 171\u2013178 (1973)","journal-title":"Discrete Math."},{"issue":"2","key":"2382_CR23","first-page":"101","volume":"1","author":"C Thomassen","year":"2010","unstructured":"Thomassen, C.: Spanning trees and orientations of graphs. J. Combin. 1(2), 101\u2013111 (2010)","journal-title":"J. Combin."},{"key":"2382_CR24","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1090\/S0002-9904-1932-05460-X","volume":"38","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: A logical expansion in mathematics. Bull. Am. Math. Soc. 38, 572\u2013579 (1932)","journal-title":"Bull. Am. Math. Soc."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02382-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-021-02382-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02382-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,13]],"date-time":"2021-11-13T21:31:00Z","timestamp":1636839060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-021-02382-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,30]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["2382"],"URL":"https:\/\/doi.org\/10.1007\/s00373-021-02382-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2021,7,30]]},"assertion":[{"value":"6 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}