The k-core and branching processes
| dc.creator | Riordan, Oliver | |
| dc.date | 2005-11-03 | |
| dc.date | 2007-02-12 | |
| dc.date.accessioned | 2026-07-07T13:12:45Z | |
| dc.date.available | 2026-07-07T13:12:45Z | |
| dc.description | The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold $λ_c$ for the emergence of a non-trivial k-core in the random graph $G(n,λ/n)$, and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or `scale-free' graph with a parameter c controlling the overall density of edges. For each k at least 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is εabove the threshold. In contrast to $G(n,λ/n)$, this fraction tends to 0 as εtends to 0. | |
| dc.description | 30 pages, 1 figure. Minor revisions. To appear in Combinatorics, Probability and Computing | |
| dc.identifier | https://arxiv.org/abs/math/0511093 | |
| dc.identifier | http://arxiv.org/abs/math/0511093 | |
| dc.identifier | Combinatorics, Probability and Computing 17 (2008) 111--136. | |
| dc.identifier | doi:10.1017/S0963548307008589 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229673 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80 | |
| dc.title | The k-core and branching processes | |
| dc.type | text |