Courses

Random Graphs Spring 2024

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, plan): Giant component.
  • Week 5 (24/06/24, plan): Clique and chromatic number.
  • 01/07/24: No class.

The following weeks will cover the following topics:

  • Planted clique.
  • Zero-one laws.
  • and more…

Assignments:

  • Assignment 1, due July 2.
  • Assignment 2: TBD.
  • Assignment 3: TBD.

OTHER SEMESTERS

  • 236306 Random Graphs Winter 2019/2020 website
  • 236646 Random Graphs Winter 2017/2018 website
  • 236646 Random Graphs Winter 2016/2017 website