Abstract | ||
---|---|---|
We establish a multivariate local limit theorem for the order and size as well as several other parameters of the k-core of the Erdős–Rényi random graph. The proof is based on a novel approach to the k-core problem that replaces the meticulous analysis of the ‘peeling process’ by a generative model of graphs with a core of a given order and size. The generative model, which is inspired by the Warning Propagation message passing algorithm, facilitates the direct study of properties of the core and its connections with the mantle and should therefore be of interest in its own right. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.jctb.2018.12.005 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Random graph,Local limit theorem,Central limit theorem,k-core | Journal | 137 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amin Coja-Oghlan | 1 | 543 | 47.25 |
Oliver Cooley | 2 | 3 | 2.13 |
Mihyun Kang | 3 | 163 | 29.18 |
kathrin skubch | 4 | 2 | 1.41 |