Name
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 k3 and fix d=np>dk. 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. (c) 2017 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/rsa.20712 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
k-core,local weak convergence,Warning Propagation,branching process | Discrete mathematics,Combinatorics,Random graph,Mantle (geology),Branching process,Mathematics | Journal |
Volume | Issue | ISSN |
51.0 | 3.0 | 1042-9832 |
Citations | PageRank | References |
1 | 0.37 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 1 | 0.37 |
| Oliver Cooley | 2 | 3 | 2.13 |
| M. Kang | 3 | 15 | 1.53 |
| kathrin skubch | 4 | 2 | 1.41 |