We will introduce a new model for random graphs, called the Poisson cloning model, in which all degrees are i.i.d. Poisson random variables. After showing how close this model is to the usual random graph model G(n,p), we will prove threshold phenomena of the k-core problem. The k-core problem is the question of when the random graph G(n,p) contains a k-core, where a k-core of a graph is a largest subgraph with minimum degree at least k.
This, in particular, improves earlier bounds of Pittel, Spencer & Wormald. The method can be easily generalized to prove similar results for random hypergraphs. If time allows, we will also discuss the scaling window of random 2-SAT and/or the giant (strong) component of random digraphs.
(work in progress.)
Copyright. All Rights Reserved.