A simple solution to the k-core problem
| dc.creator | Janson, Svante | |
| dc.creator | Luczak, Malwina | |
| dc.date | 2005-08-24 | |
| dc.date.accessioned | 2026-07-07T05:22:37Z | |
| dc.date.available | 2026-07-07T05:22:37Z | |
| dc.description | 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). Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/math/0508453 | |
| dc.identifier | http://arxiv.org/abs/math/0508453 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76133 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80 | |
| dc.title | A simple solution to the k-core problem | |
| dc.type | text |