Random graphs
Béla Bollobás · Cambridge University Press eBooks · 2010
The aim of this review is to highlight some of the fundamental results about random graphs, mostly in areas I am particularly interested in. Though a fair number of references are given, the review is far from complete even in the topics it covers. Furthermore, very few of the proofs are indicated. The exception is the last section, which concerns random regular graphs. This section contains some very recent results and we present some proofs in a slightly simplified form. The study of random graphs was started by Erdòs [33], who applied random graph techniques to show the existence of a graph of large chromatic number and large girth. A little later Erdös and Rényi [38] investigated random graphs for their own sake. They viewed a graph as an organism that develops by acquiring more and more edges in a random fashion. The question is at what stage of development a graph is likely to have a given property. The main discovery of Erdös and Rényi was that many properties appear rather suddenly. In the last twenty years many papers have been written about random graphs; some of them, in the vein of [33], tackle traditional graph problems by the use of random graphs, and others, in fact the majority, study the standard invariants of random graphs in the vein of [38]. Of course the two trends cannot really be separated for deep applications are impossible without detailed knowledge of random graphs.