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 backround. 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, plan): Zero-one laws and other topics in the logic of random graphs.
The following weeks will cover the following topics:
- Expanders.
- and possibly more…
Assignments:
