21-801: Random Graphs, Spring 2012
Tuesday 3.30-5.30 Wean Hall 8201
Thursday 2.30-3.30 Wean Hall 8201

Monday 2.30-3.30 Wean Hall 7130
(only for people that cannot make the Thursday class).

Grading Policy:
There will be four in class tests worth 25% each.
A: 85%+
B: 75%--84%
C: 65%--74%
D: 50%--64%
R: 0%--49%

Exam Schedule (Provisional):


Test 1: Thursday, February 16, 2012

Test 2: Thursday, March 8, 2012

Test 3: Thursday, April 12, 2012.

Test 4: Thursday, May 3, 2012.

There will individual arrangements for those that cannot take the Thursday class.

Each test will have two questions. The tests will be closed book. Exercises Course Notes, in addition to the manuscript provided. 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