{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:44Z","timestamp":1760202764405},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T00:00:00Z","timestamp":1522800000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>In this paper we consider<jats:italic>j<\/jats:italic>-tuple-connected components in random<jats:italic>k<\/jats:italic>-uniform hypergraphs (the<jats:italic>j<\/jats:italic>-tuple-connectedness relation can be defined by letting two<jats:italic>j<\/jats:italic>-sets be connected if they lie in a common edge and considering the transitive closure; the case<jats:italic>j<\/jats:italic>= 1 corresponds to the common notion of vertex-connectedness). We show that the existence of a<jats:italic>j<\/jats:italic>-tuple-connected component containing \u0398(<jats:italic>n<\/jats:italic><jats:sup><jats:italic>j<\/jats:italic><\/jats:sup>)<jats:italic>j<\/jats:italic>-sets undergoes a phase transition and show that the threshold occurs at edge probability<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S096354831800010X_eqnU1\" \/><jats:tex-math>$$\\frac{(k-j)!}{\\binom{k}{j}-1}n^{j-k}.$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>Our proof extends the recent short proof for the graph case by Krivelevich and Sudakov, which makes use of a depth-first search to reveal the edges of a random graph.<\/jats:p><jats:p>Our main original contribution is a<jats:italic>bounded degree lemma<\/jats:italic>, which controls the structure of the component grown in the search process.<\/jats:p>","DOI":"10.1017\/s096354831800010x","type":"journal-article","created":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T10:18:48Z","timestamp":1522837128000},"page":"741-762","source":"Crossref","is-referenced-by-count":9,"title":["Largest Components in Random Hypergraphs"],"prefix":"10.1017","volume":"27","author":[{"given":"OLIVER","family":"COOLEY","sequence":"first","affiliation":[]},{"given":"MIHYUN","family":"KANG","sequence":"additional","affiliation":[]},{"given":"YURY","family":"PERSON","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,4,4]]},"reference":[{"key":"S096354831800010X_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20585"},{"key":"S096354831800010X_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S096354831800010X_ref4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/rsa.20282","article-title":"The order of the giant component of random hypergraphs.","volume":"36","author":"Behrisch","year":"2010","journal-title":"Random Struct. Alg."},{"key":"S096354831800010X_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000017"},{"key":"S096354831800010X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9483-8"},{"key":"S096354831800010X_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00464-2"},{"key":"S096354831800010X_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S096354831800010X_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010305"},{"key":"S096354831800010X_ref7","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"S096354831800010X_ref20","first-page":"350","volume-title":"COCOON 2006: Computing and Combinatorics","author":"Ravelomanana","year":"2006"},{"key":"S096354831800010X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20495"},{"key":"S096354831800010X_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0019-8"},{"key":"S096354831800010X_ref10","article-title":"The size of the giant component in random hypergraphs","author":"Cooley","journal-title":"Random Struct. Alg."},{"key":"S096354831800010X_ref16","unstructured":"Lu L. and Peng X. High-order phase transition in random hypergraphs. arXiv:1409.1174"},{"key":"S096354831800010X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0027-9"},{"key":"S096354831800010X_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20470"},{"key":"S096354831800010X_ref11","first-page":"17","article-title":"On the evolution of random graphs.","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S096354831800010X_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579445"},{"key":"S096354831800010X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.02.018"},{"key":"S096354831800010X_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20456"},{"key":"S096354831800010X_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831800010X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T01:10:55Z","timestamp":1604106655000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831800010X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,4]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S096354831800010X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831800010x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,4]]}}}