During the 2019–2020 winter semester, I gave a class on random graphs, based in large part on Introduction to random graphs by Alan Frieze and Michał Karoński.
Class involves three assignments and a final project. The teaching assistant is Dor Katzelnick.
Some material from past offering of the class: lecture notes and a review of probability theory prepared by legendary teaching assistant Itay Hazan.
Here is what we covered in class:
- Week 1 (23/10/2019): Models of random graphs. Threshold for appearance of triangles.
- Week 2 (30/10/2019): Thresholds for general graphs.
- Week 3 (06/11/2019): Distribution at the threshold (probability of no triangles).
- Week 4 (13/11/2019): Distribution at the threshold (rest of the distribution).
- Week 5 (20/11/2019): Connectivity.
- Week 6 (27/11/2019): Ramsey theory and cliques.
- Week 7 (04/12/2019): Finding cliques in random graphs. Planted clique.
- Week 8 (11/12/2019): Spectral techniques for planted clique.
- Week 9 (18/12/2019): Zero-one laws.
- Week 10 (01/01/2020): Quasirandom graphs and graphons.
- Week 11 (08/01/2020): Dijkstra’s algorithm and Kruskal’s algorithm on randomly weighted graphs.
- Week 12 (15/01/2020): Expanders (guest lecture by Marc Vinyals).
- Week 13 (22/01/2020): Regularity lemma (guest lecture by Nitin Saurabh).
Assignments:
Assignment 3 was quite a bit harder than the preceding ones.
