How does the core sit inside the mantle?1. Issue 3 (10th April 2017) - Coja‐Oghlan, Amin; Cooley, Oliver; Kang, Mihyun; Skubch, Kathrin
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