The theory of random graphs, founded by Erdös and Rényi in the late 1950s, has grown into a large and very active area. In the last decade, many powerful new methods have been discovered to tackle more and more intricate problems. In this course we shall present several classical results of the theory, together with numerous recent developments that illustrate the use of great many tools.

In particular, we shall prove he fundamental inequalities of combinatorial probability: the lemma of Harris, the Four Functions inequality, the Lovász local lemma, and the inequalities of Azuma, Janson, and Talagrand. These inequalities will be applied to study the basic models of random graphs: G(n, p) and G(n, m), the space of random graph processes, and threshold functions of monotone properties, in particular, those of connectedness, 1-factors, Hamilton cycles, the diameter and the chromatic number.

We shall also examine the phase transition in the component structure, including the order of the giant component close to the critical probability, and prove some as yet unpublished results about the chromatic number and the random assignment problem.

Finally, we hope to present several models of large-scale real-life networks and prove some very recent results about them.

The course will be accessible to people with a rudimentary knowledge of combinatorics and probability theory: the main requirement is mathematical maturity.

Zeit:       Dienstag 10-12
Ort:        HG G 43 (Hermann-Weyl-Zimmer)
Beginn:   6. April
 

M. Struwe