A simple solution to the k-core problem
We study the k-core of a random (multi) graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k-core is empty, and other conditions that imply that with high probability the k-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer and Wormald on the existence and size of a k-core in G(n,p) and G(n,m), see also Molloy and Cooper.
Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.
This is joint work with Svante Janson.
Speaker Details
Malwina Luczak received her Ph. D. from the University of Oxford in 2001. She joined the LSE’s faculty in 2003. Before then she was a temporary faculty member at the Statistical Laboratory, Cambridge (2001-2003), and a Junior Research Fellow at Wadham College, Oxford (2000-2001). She works in Probability Theory and Discrete Mathematics. Her main interests are quantitative limit theorems for Markov chains in infinite dimensions and phase transitions in random interacting systems.
- Date:
- Speakers:
- Malwina Luczak
- Affiliation:
- London School of Economics
-
-
Jeff Running
-
