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
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)
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)
March 19
Janson's inequalities; the probability of nonexistence of a given subgraph in G(n,p); distributions determined by their moments; the method of moments; the limiting distribution of the number of copies of a fixed strictly balanced graph in G(n,p)
April 9
thresholds for a given minimum degree; the hitting time of connectivity; the Galton–Watson process: the definition and the extinction probability; the emergence of the giant component in G(n, c/n)
April 16
upper bounds for tails of the binomial distribution; the phase transition in G(n, c/n) – statement and proof and component structure in the subcritical regime (c < 1)
April 23
the phase transition in G(n, c/n) – long paths in the supercritical regime (c > 1); perfect matchings in G(n,n,p)
April 30
perfect matchings in G(n,p); the independence number of dense random graphs
May 7
the chromatic number of dense random graphs; martingales; the Azuma–Hoeffding inequality; concentration of the chromatic number of G(n,p)
May 14
two-point concentration of the chromatic number of sparse G(n,p); random graphs with a fixed degree sequence; the configuration model; counting graphs with a given degree sequence
May 21
counting graphs with a given degree sequence; the "switching" lemma
May 28
Posá's rotation–extention technique; the threshold for Hamiltonicity of G(n,p)