Core forging and local limit theorems for the k-core of random graphs
Preprint
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 Erdos-Renyi 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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The stripping process can be slow: Part IRandom Structures & Algorithms, 2018
- The Stripping Process Can be Slow: Part IISIAM Journal on Discrete Mathematics, 2018
- The solution space geometry of random linear equationsRandom Structures & Algorithms, 2013
- Finite size scaling for the core of large random hypergraphsThe Annals of Applied Probability, 2008
- Asymptotic normality of the k-core in random graphsThe Annals of Applied Probability, 2008
- The cores of random hypergraphs with a given degree sequenceRandom Structures & Algorithms, 2004
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001
- An elementary proof of the local central limit theoremJournal of Theoretical Probability, 1995
- A new bijection on rooted forestsDiscrete Mathematics, 1993
- Size and connectivity of the k-core of a random graphDiscrete Mathematics, 1991