Courses

236646 Random Graphs Winter 2017/2018

During the 2017–2018 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.

I prepared lecture notes, and the teaching assistant Itay Hazan prepared a review of probability theory.

Here are the subjects we have covered in class (with pointers to the lecture notes):

  • Week 1 (22 Oct 2017): Introduction (Section 1).
  • Week 2 (29 Oct 2017): Sparse random graphs (Section 2).
  • Week 3 (5 Nov 2017): Subcritical regime (Section 3), except for the lower bound in Theorem 3.2.
  • Week 4 (12 Nov 2017): Completion of the proof of Theorem 3.2; introduction to the supercritical regime (Section 4).
  • Week 5 (19 Nov 2017): Supercritical regime (Section 4).
  • Week 6 (26 Nov 2017): Connectivity (Section 6).
  • Week 7 (3 Dec 2017): Subgraph thresholds (Section 7.1).
  • Week 8 (10 Dec 2017): Thresholds (Section 8).
  • Week 9 (24 Dec 2017): Maximum clique (Section 9.1), chromatic number (Section 9.2).
  • Week 10 (31 Dec 2017): Finding cliques in random graphs (Section 9.3), introduction to planted clique (Section 10.1).
  • Week 11 (7 Jan 2018): Spectral algorithm for planted clique (Sections 10.3 and 10.5).
  • Week 12 (14 Jan 2018): Random regular graphs (Section 11).
  • Week 13 (21 Jan 2018): Expanders (Section 12), guest lecture by Roy Schwartz.

Assignments:

OTHER SEMESTERS

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