Random graphs (Spring 2021)

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

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.

Textbooks

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 (online version available here)

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 8
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; every monotone property has a threshold (Bollobás–Thomason)
March 15
Sharp thresholds; hitting times; thresholds for appearance of small subgraphs; Harris's inequality
March 22
Lower bounds for the probability of nonexistence; Janson's inequality; the probability of nonexistence of a given subgraph in G(n,p); distributions determined by their moments; the method of moments; lower tails for subgraph counts in G(n,p)
April 5
Upper tails for subgraph counts in G(n,p); thresholds for a given minimum degree; the hitting time of connectivity; the Galton–Watson process: the definition and the extinction probability
April 12
The extinction probability of the Galton–Watson process; upper bounds for tails of the binomial distribution; the emergence of the giant component in G(n, c/n)
April 19
Long paths in the supercritical regime (c > 1); perfect matchings in G(n,n,p); perfect matchings in G(n,p)
April 26
Perfect matchings in G(n,p) (continued); the independence number of dense random graphs
May 3
the chromatic number of dense random graphs; martingales; the Azuma–Hoeffding inequality; concentration of the chromatic number of G(n,p)
May 10
Posá's rotation–extention technique; the threshold for Hamiltonicity of G(n,p)
May 24
Random graphs with a fixed degree sequence; the configuration model; counting graphs with a given degree sequence; the "switching" lemma
May 31
Random graphs with a given degree sequence (ctd); a sufficient condition for the appearance of a spanning subgraph in G(n,p) (the Alon–Füredi theorem); the threshold for Hamiltonicity in D(n,p)
June 7
Lower bounds for off-diagonal Ramsey numbers (Krivelevich); an exponential improvement of the lower bound for R(t,t,t) due to Conlon–Ferber; the Turán problem in random graphs
June 14
The container theorem for H-free graphs (without proof); the Erdős–Stone theorem in random graphs; Ramsey's theorem in random graphs (1-statement)