Date  Topic  Homework  Due  
1  1/17  History and models of random graphs 
HW#1 Problems: 1,2,3 from slide 8 
1/22 
2  1/22  Monotonicity and equivalence of 2 basic models 
HW#2 Problems: 4,5,6 from slide 8 
1/29 
3 
1/24  Equivalence and thresholds  HW#3 Problem 7,8 from slide 8  1/29 
4 
1/29  Threshold for isolates and connectedness 

5 
1/31  Subcritical phase  HW#4: Problem 9 from slide 8 plus finish the proof from class  2/5 
6 
2/5  Subcritical phase (cont.) 

7 
2/7  Thresholds for small subgraphs 
HW#5 Problems 1012 from slide 13  
8 
2/12  Poisson distribution of strictly balanced graphs at the
threshold 
HW#6 Problems 13,14 from slide 13 plus 12 in general form
plus the kth factorial moment of Poisson 

9 
2/14  Perfect matchings in random bipartite graphs 

10  2/19  Hamilton cycles in random graphs  Posa transforms and
theorem 

11  2/21  Homework solving 
read Mitzenmacher and Upfal about a Ham. cycle algorithm 

12  2/26  A randomized algorithm for a Ham. cycle in G(n,p)


13  2/28  A randomized algorithm for a Ham. cycle in G(n,p) (cont.) 

14  3/4  Perfect matchings in random graphs (ErdosRenyi 1966) 
Damoa 

15  3/6  Perfect matchings in random graphs (ErdosRenyi 1966) 
Kinnari 

16  3/18  Hamiltonian cycles  refinement. Chernoff's bounds 

17  3/20  Janson's inequality 
HW#7 Problems 15,16,18,19 from slide 32 
4/1 
18  3/25  Applicartions of Janson's inequality 

19 
3/27  AzumaHoeffding and Talagrand inequalities 


20  4/1  Chromatic number and Ramsey properties of random graphs 
HW#8 Problems 2025 from slide 43  4/24 
21  4/3  HaberKrivelevich paper  Daniel 


22  4/8  HaberKrivelevich paper  Silke 

23  4/10  HaberKrivelevich paper  Daniel/Silke 

24  4/15  JohanssonKahnVu paper 

25  4/17  JohanssonKahnVu paper 

26  4/22  JohanssonKahnVu paper 

27  4/24 
JohanssonKahnVu paper 