Random graphs (Spring 2018)

Lecturer: Wojciech Samotij
e-mail: samotij(at)post.tau.ac.il
Course #: 0366-5085-01
Monday, 16:10–19:00
Orenstein 110

Office hours:
Wednesday, 14:00–15:00
Schreiber 002

Course description

This is an introductory course on random graphs. Among topics that will be covered are the following: models of random graphs and random graph processes; threshold functions for graph properties; the appearance of small subgraphs; the evolution of random graphs and the appearance of the giant component; connectivity and matchings; long paths and cycles; the independence and chromatic numbers; random regular graphs and the configuration model; pseudo-random graphs; additional topics (if time permits)

The students enrolling in the course are expected to have working knowledge of basic notions in graph theory and be familiar with basic concepts of discrete probability.

The final grade will be determined by a take-home exam at the end of the semester.

The course will be taught in English.


S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley, 2000
B. Bollobás, Random graphs, Cambridge University Press, 2001 (2nd edition)
A. Frieze and M. Karoński, Introduction to random graphs, Cambridge University Press, 2016

Further reading

M. Karoński and A. Ruciński, The origins of the theory of random graphs in The mathematics of Paul Erdős I, Springer, 2013 (2nd edition)

Course outline

March 5
Historical remarks on the origins of the theory of random graphs; two models of random graphs – G(n,p) and G(n,m); random graph processes; properties and monotone properties; Pittel's inequality and its strengthening for monotone properties; asymptotic equivalence of G(n,p) and G(n,m); threshold functions; multi-round exposure
March 12
Every monotone property has a threshold (Bollobás–Thomason); sharp thresholds; hitting times; thresholds for appearance of small subgraphs; Harris' inequality and lower bounds for the probability of nonexistence; Janson's inequality (without proof)