Courses

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:

• Assignment 0, not for submission (review of probability theory).
• Assignment 1, due Nov 19. Solution.
• Assignment 2, due Dec 10. Solution.
• Assignment 3, due Jan 7. Solution.
• Assignment 4 (optional), due Mar 20. This assignment was required to obtain a grade beyond 95.