21-801: Random Graphs, Spring 2017
Monday 3.30-5.00 Porter Hall A20
Wednesday 3.30-5.00 Porter Hall A20

We will follow the book
Introduction to Random Graphs
Alan Frieze and Michal Karonski

Suggested Exercises

Old Notes, in addition to the book.

1. Very sparse graphs o(n) edges I.
2. Very sparse graphs o(n) edges II.
3. Sparse graphs cn/2 edges. c<1.
4. Sparse graphs cn/2 edges. c>1.
5. Branching Processes
6. Connectivity of Random Graphs
7. Perfect Matchings in Random Graphs
8. Hamilton Cycles in Random Graphs
9. Seperation of High Degrees, Chromatic Index and Graph Isomorphism
10. Janson's Inequality
11. Diameter of Random Graphs
12. Coloring Random Graphs
13. Concentration Inequalities from Martingales
14. Small Subgraphs
15. Every Monotone Property has a Threshold
16. Expected Length of the Minimum Spanning Tree
17. Random Graphs with a Fixed Degree Sequence
18. Differential Equations Method
19. Eigenvalues of Random Graphs
20. Preferential Attachment
21. Largest Component: ~n/2 edges.
22. Perfect Matchings in Bipartite 2-out
23. Random Mappings
24. Shortest Paths
25. Digraphs