MATH-737 Random Structures

%

Syllabus


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 10-12 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 k-th 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 (Erdos-Renyi 1966) -- Damoa
15 3/6 Perfect matchings in random graphs (Erdos-Renyi 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 Azuma-Hoeffding and Talagrand inequalities

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

22 4/8 Haber-Krivelevich paper - Silke
23 4/10 Haber-Krivelevich paper - Daniel/Silke
24 4/15 Johansson-Kahn-Vu paper
25 4/17 Johansson-Kahn-Vu paper
26 4/22 Johansson-Kahn-Vu paper

27 4/24
Johansson-Kahn-Vu paper