Preface

These lecture notes are intended to be used for master courses, where the students have a limited prior knowledge of special topics in probability. Therefore, we have included many of the preliminaries, such as convergence of random variables, probabilistic bounds, coupling, martingales and branching processes. These notes are aimed to be self-contained, and to give the readers an insight in the history of the field of random graphs. The field of random graphs was started in 1959-1960 by Erdős and Rényi, see [109, 110, 111, 112]. At first, the study of random graphs was used to prove deterministic properties of graphs. For example, if we can show that a random graph has with a positive probability a certain property, then a graph must exist with this property. The method of proving deterministic statements using probabilistic arguments is called the probabilistic method, and goes back a long way. See among others the preface of a standard work in random graphs by Bollobás [52], or the work devoted to it The Probabilistic Method [14]. Erdős was one of the first to use this method, see e.g., [107], where it was shown that the Ramsey number R(k) is at least 2k/2. The Ramsey number R(k) is the value n for which any graph of size at least n is such that either itself or its complement contains a complete graph o