Courses

236306 Random Graphs Winter 2019/2020

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.

OTHER SEMESTERS

  • Random Graphs Spring 2024 website
  • 236646 Random Graphs Winter 2017/2018 website
  • 236646 Random Graphs Winter 2016/2017 website