{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T03:24:15Z","timestamp":1779161055345,"version":"3.51.4"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T00:00:00Z","timestamp":1621987200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> denote a uniformly random <jats:italic>r<\/jats:italic>-regular <jats:italic>s<\/jats:italic>-uniform hypergraph on the vertex set {1, 2, \u2026 , <jats:italic>n<\/jats:italic>}. We establish a threshold result for the existence of a spanning tree in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, restricting to <jats:italic>n<\/jats:italic> satisfying the necessary divisibility conditions. Specifically, we show that when <jats:italic>s<\/jats:italic>\u00a0\u2265\u00a05, there is a positive constant <jats:italic>\u03c1<\/jats:italic>(<jats:italic>s<\/jats:italic>) such that for any <jats:italic>r<\/jats:italic>\u00a0\u2265\u00a02, the probability that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a spanning tree tends to 1 if <jats:italic>r<\/jats:italic> &gt; <jats:italic>\u03c1<\/jats:italic>(<jats:italic>s<\/jats:italic>), and otherwise this probability tends to zero. The threshold value <jats:italic>\u03c1<\/jats:italic>(<jats:italic>s<\/jats:italic>) grows exponentially with <jats:italic>s<\/jats:italic>. As <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is connected with probability that tends to 1, this implies that when <jats:italic>r<\/jats:italic> \u2264 <jats:italic>\u03c1<\/jats:italic>(<jats:italic>s<\/jats:italic>), most <jats:italic>r<\/jats:italic>-regular <jats:italic>s<\/jats:italic>-uniform hypergraphs are connected but have no spanning tree. When <jats:italic>s<\/jats:italic>\u00a0=\u00a03, 4 we prove that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a spanning tree with probability that tends to 1, for any <jats:italic>r<\/jats:italic>\u00a0\u2265\u00a02. Our proof also provides the asymptotic distribution of the number of spanning trees in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000158_inline1.png\"\/><jats:tex-math>$${{\\mathcal G}_{n,r,s}}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for all fixed integers <jats:italic>r<\/jats:italic>, <jats:italic>s<\/jats:italic>\u00a0\u2265\u00a02. Previously, this asymptotic distribution was only known in the trivial case of 2-regular graphs, or for cubic graphs.<\/jats:p>","DOI":"10.1017\/s0963548321000158","type":"journal-article","created":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T13:39:42Z","timestamp":1622036382000},"page":"29-53","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Spanning trees in random regular uniform hypergraphs"],"prefix":"10.1017","volume":"31","author":[{"given":"Catherine","family":"Greenhill","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Isaev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary","family":"Liang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,5,26]]},"reference":[{"key":"S0963548321000158_ref25","volume-title":"Counting Labelled Trees","author":"Moon","year":"1970"},{"key":"S0963548321000158_ref21","unstructured":"[21] Kajino, H. (2019) Molecular hypergraph grammar with its application to molecular optimization. In Proceedings of Machine Learning Research, Vol. 97, PMLR, pp. 3183\u20133191."},{"key":"S0963548321000158_ref2","doi-asserted-by":"crossref","first-page":"112192","DOI":"10.1016\/j.disc.2020.112192","article-title":"The average number of spanning hypertrees in sparse uniform hypergraphs","volume":"344","author":"Aldosari","year":"2021","journal-title":"Discrete Math."},{"key":"S0963548321000158_ref31","unstructured":"[31] Sivasubramanian, S. Spanning trees in complete uniform hypergraphs and a connection to extended r-Shi hyperplane arrangements. arXiv:math\/0605083."},{"key":"S0963548321000158_ref33","volume-title":"Generatingfunctionology","author":"Wilf","year":"1994"},{"key":"S0963548321000158_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20460"},{"key":"S0963548321000158_ref11","doi-asserted-by":"crossref","unstructured":"[11] Brault-Baron, J. (2015) Hypergraph acyclicity revisited. ACM Comput. Surv. 49(3) article 54.","DOI":"10.1145\/2983573"},{"key":"S0963548321000158_ref23","volume-title":"Elementary Classical Analysis","author":"Marsden","year":"1974"},{"key":"S0963548321000158_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.11.001"},{"key":"S0963548321000158_ref12","first-page":"37","article-title":"On an extension of a partition identity and its Abel-analog","volume":"6","author":"Chu","year":"1986","journal-title":"J. Math. Res. Exposition"},{"key":"S0963548321000158_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662157.006"},{"key":"S0963548321000158_ref19","first-page":"1","article-title":"On the number of spanning trees in random regular graphs","volume":"21","author":"Greenhill","year":"2014","journal-title":"Electr. J. Comb."},{"key":"S0963548321000158_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001796"},{"key":"S0963548321000158_ref32","unstructured":"[32] Warme, D. M. (1998) Spanning Trees in Hypergraphs with Applications to Steiner Trees. Ph.D Thesis, University of Virginia."},{"key":"S0963548321000158_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"S0963548321000158_ref30","unstructured":"[30] Siu, W.-C. (2002) Hypertrees in d-uniform hypergraphs, Ph.D. thesis, Michigan State University. Available from https:\/\/search.proquest.com\/docview\/305546157?pq-origsite=primo."},{"key":"S0963548321000158_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"S0963548321000158_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990654"},{"key":"S0963548321000158_ref10","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/BFb0073123","volume-title":"Graphs Theory Singapore 1983","volume":"1073","author":"Boonyasombat","year":"1984"},{"key":"S0963548321000158_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"S0963548321000158_ref24","first-page":"213","article-title":"Subgraphs of random graphs with specified degrees","volume":"33","author":"McKay","year":"1981","journal-title":"Conguressus Numerantium"},{"key":"S0963548321000158_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"S0963548321000158_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548321000158_ref14","first-page":"381","volume-title":"Handbook of Combinatorics","volume":"1","author":"Duchet","year":"1995"},{"key":"S0963548321000158_ref4","unstructured":"[4] Bacher, R. On the enumeration of labelled hypertrees and of labelled bipartite trees. arXiv:1102.2708"},{"key":"S0963548321000158_ref35","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1017\/CBO9780511721335.010","volume-title":"Surveys in Combinatorics, 1999","volume":"267","author":"Wormald","year":"1999"},{"key":"S0963548321000158_ref7","volume-title":"Graphs and Hypergraphs","author":"Berge","year":"1976"},{"key":"S0963548321000158_ref1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ejc.2018.11.002","article-title":"Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges","volume":"77","author":"Aldosari","year":"2019","journal-title":"Eur. J. Comb."},{"key":"S0963548321000158_ref15","unstructured":"[15] Dumitriu, I. and Zhu, Y. Spectra of random regular hypergraphs. arXiv:1905.06487."},{"key":"S0963548321000158_ref29","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/57"},{"key":"S0963548321000158_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9137-z"},{"key":"S0963548321000158_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80021-4"},{"key":"S0963548321000158_ref22","unstructured":"[22] Lavault, C. A note on Pr\u00fcfer-like coding and counting forests of uniform hypertrees. arXiv:1110.0204."},{"key":"S0963548321000158_ref17","unstructured":"[17] Greenhill, C. , Isaev, M. and Liang, G. Spanning trees in random regular uniform hypergraphs. arXiv:2005.07350."},{"key":"S0963548321000158_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T10:38:37Z","timestamp":1639996717000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000158\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,26]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["S0963548321000158"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000158","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,26]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}