How does the core sit inside the mantle?

Abstract

Abstract The k ‐core, defined as the maximal subgraph of minimum degree at least k , of the random graph 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 and fix . Colour each vertex that belongs to the k ‐core of 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

Locations

• arXiv (Cornell University) - View - PDF
• Random Structures and Algorithms - View