How does the core sit inside the mantle?1. Issue 3 (10th April 2017)

• Record Type: Journal Article
• Authors: Coja‐Oghlan, Amin; Cooley, Oliver; Kang, Mihyun; Skubch, Kathrin
• Is Part Of: Random structures & algorithms. Volume 51:Issue 3(2017)
• Page Start: 459
• Page End: 482
• Publication Date: 2017-04-10
• Subjects: k‐core -- local weak convergence -- Warning Propagation -- branching process; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20712
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The k ‐core, defined as the maximal subgraph of minimum degree at least k, of the random graph G ( n, p ) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold d k for the appearance of an extensive k ‐core. The aim of the present paper is to describe how the k ‐core is "embedded" into the random graph in the following sense. Let k ≥ 3 and fix d = n p > d k . Colour each vertex that belongs to the k ‐core of G ( n, p ) in black and all remaining vertices in white. Here we derive a multi‐type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k ‐core. 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–2808] used this characterization to describe the 2‐core 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 k ‐core. Based on this the study of the k ‐core reduces to the analysis of Warning Propagation on a suitable Galton‐Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 459–482, 2017