Random Graphs

Course description

This course introduces probabilistic methods in graph theory and the classical Erdős–Rényi random graph models.

Materials

• Lecture notes
• Seminar notes
• Problem sets
• Research problems

Topics

1. The models (G(n,p)) and (G(n,m))
2. Threshold functions
3. Subgraph counts
4. The first and second moment methods
5. Connectivity
6. Independence and clique numbers
7. Chromatic number
8. Random graph logic