During the 2024 spring semester, I am giving a class on random graphs, based in large part on Introduction to random graphs by Alan Frieze and Michał Karoński. Lecture notes for the class will be prepared as we go. Itay Hazan’s notes on elementary discrete probability are useful background. There will be about three problem sets. Here is what we covered in class:
- Week 1 (27/05/24): Class overview. Models of random graphs. Threshold for the appearance of triangles.
- Week 2 (03/06/24): Asymptotic distribution of number of triangles. Thresholds for appearance of other subgraphs. Statement of Kahn–Kalai conjecture.
- Week 3 (10/06/24): Connectivity threshold. Hitting time version.
- Week 4 (17/06/24): Giant component.
- Week 5 (24/06/24): Clique and chromatic number.
- 01/07/24: No class.
- Week 6 (08/07/24): Chromatic number: concentration and anti-concentration.
- Week 7 (15/07/24): Finding cliques in random graphs. Planted clique: degree-based algorithm and partial enumeration.
- Week 8 (22/07/24): Planted clique: spectral algorithms.
- Week 9 (29/07/24): Zero-one law for dense random graphs.
- Week 10 (05/08/24): Zero-one law for sparse random graphs. Random bipartite regular graphs.
- Week 11 (12/08/24): Expanders.
- Week 12 (19/08/24): No class.
Assignments:
