{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:22:33Z","timestamp":1758824553555},"reference-count":27,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2017,4,10]],"date-time":"2017-04-10T00:00:00Z","timestamp":1491782400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P26826; W1230"],"award-info":[{"award-number":["P26826; W1230"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>k<\/jats:italic>\u2010core, defined as the maximal subgraph of minimum degree at least <jats:italic>k<\/jats:italic>, of the random graph <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20712-math-0001.png\" xlink:title=\"urn:x-wiley:10429832:media:rsa20712:rsa20712-math-0001\" \/> has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111\u2013151] determined the threshold <jats:italic>d<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> for the appearance of an extensive <jats:italic>k<\/jats:italic>\u2010core.<\/jats:p><jats:p>The aim of the present paper is to describe how the <jats:italic>k<\/jats:italic>\u2010core is \u201cembedded\u201d into the random graph in the following sense. Let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20712-math-0002.png\" xlink:title=\"urn:x-wiley:10429832:media:rsa20712:rsa20712-math-0002\" \/> and fix <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20712-math-0003.png\" xlink:title=\"urn:x-wiley:10429832:media:rsa20712:rsa20712-math-0003\" \/>. Colour each vertex that belongs to the <jats:italic>k<\/jats:italic>\u2010core of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20712-math-0004.png\" xlink:title=\"urn:x-wiley:10429832:media:rsa20712:rsa20712-math-0004\" \/> in black and all remaining vertices in white. Here we derive a multi\u2010type branching process that describes the local structure of this coloured random object as <jats:italic>n<\/jats:italic> tends to infinity. This generalises prior results on, e.g., the internal structure of the <jats:italic>k<\/jats:italic>\u2010core.<\/jats:p><jats:p>In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743\u20132808] used this characterization to describe the 2\u2010core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the <jats:italic>k<\/jats:italic>\u2010core. Based on this the study of the <jats:italic>k<\/jats:italic>\u2010core reduces to the analysis of Warning Propagation on a suitable Galton\u2010Watson tree. \u00a9 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 459\u2013482, 2017<\/jats:p>","DOI":"10.1002\/rsa.20712","type":"journal-article","created":{"date-parts":[[2017,4,10]],"date-time":"2017-04-10T10:07:19Z","timestamp":1491818839000},"page":"459-482","source":"Crossref","is-referenced-by-count":4,"title":["How does the core sit inside the mantle?"],"prefix":"10.1002","volume":"51","author":[{"given":"Amin","family":"Coja\u2010Oghlan","sequence":"first","affiliation":[{"name":"Department of Discrete Mathematics Goethe University, Mathematics Institute 10 Robert Mayer St Frankfurt 60325 Germany"}]},{"given":"Oliver","family":"Cooley","sequence":"additional","affiliation":[{"name":"Combinatorics Group, Graz University of Technology, Institute of Discrete Mathematics Steyrergasse 30 8010 Graz Austria"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[{"name":"Combinatorics Group, Graz University of Technology, Institute of Discrete Mathematics Steyrergasse 30 8010 Graz Austria"}]},{"given":"Kathrin","family":"Skubch","sequence":"additional","affiliation":[{"name":"Department of Discrete Mathematics Goethe University, Mathematics Institute 10 Robert Mayer St Frankfurt 60325 Germany"}]}],"member":"311","published-online":{"date-parts":[[2017,4,10]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"crossref","unstructured":"D.AchlioptasandA.Coja\u2010Oghlan Algorithmic barriers from phase transitions In Proceedings of 49th FOCS IEEE Philadelphia 2008 pp.793\u2013802.","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005936"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09444-0_1"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v6-96"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0590-8"},{"key":"e_1_2_7_9_1","doi-asserted-by":"crossref","first-page":"R81","DOI":"10.37236\/1107","article-title":"Encores on cores","volume":"13","author":"Cain J.","year":"2006","journal-title":"Electron J Combin"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-PS121"},{"key":"e_1_2_7_12_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s P.","year":"1960","journal-title":"Magayar Tud Akad Mat Kutato Int Kozl"},{"key":"e_1_2_7_13_1","unstructured":"D.FernholzandV.Ramachandran The giantk\u2010core of a random graph with a specified degree sequence 2003."},{"key":"e_1_2_7_14_1","unstructured":"D.FernholzandV.Ramachandran Cores and connectivity in sparse random graphs UTCS Technical Report TR04\u201013 Citeseer Pennsylvania 2004."},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1060"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20147"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP478"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010106"},{"key":"e_1_2_7_20_1","doi-asserted-by":"crossref","unstructured":"J. H.Kim Poisson cloning model for random graphs Proceedings of the International Congress of Mathematicians Madrid 2006 pp.873\u2013897.","DOI":"10.4171\/022-3\/43"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90162-U"},{"key":"e_1_2_7_22_1","first-page":"165","volume-title":"Random graphs 2","author":"\u0141uczak T.","year":"1992"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214060"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0036"},{"key":"e_1_2_7_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008589"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2014.03.007"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20712","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T16:24:07Z","timestamp":1696350247000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,10]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.1002\/rsa.20712"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20712","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,10]]}}}