Class InfoClass Number: Math 736Dates: Sep 1, 2015  Dec 1, 2015 Room: NS B06 Meeting time:
Purpose: Introduction to the theory and applications of the Probabilistic Method in Combinatorics. Text: Jiří Matoušek, Jan Vondrák, The Probabilistic Method Other supporting literature: Laszlo Lovász, Random Walks on Graphs: A Survey Stefan H.M. van Zwam, Combinatorial Mathematics 

Week  Topics  Chapters 
1  Probability Theory  1.1,1.2 
2  Ramsey Theory  2.1,2.2 
3  ErdősKoRado Theorem  2.3,2.4 
4  Linearity of Expectation  3 
5  Independent Sets  4 
6  Second Moment  5.1,5.2 
7  Midterm  
8  Threshold Functions  5.3 
9  The Clique Number  5.4 
10  Lovász Local Lemma  6.1,6.2,6.3 
11  Coloring of Real Numbers  6.4,6.5 
12  Strong Concentration  7.1,7.2 
13  Binomial Distribution Bound  7.3 
14  Sum of Dependent Variables  7.4 
15  Final Exam 
Attendance  10% 
Midterm:  40% 
Final:  50% 