Combinatorics 1 (조합론)

Class Info

Class Number: Math 736
Dates: Sep 1, 2015 - Dec 1, 2015
Room: NS B06
Meeting time:
Tuesday 15:00 - 17:45

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
Links
Homework

Syllabus

Week Topics Chapters
1 Probability Theory 1.1,1.2
2 Ramsey Theory 2.1,2.2
3 Erdős-Ko-Rado 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

Grading

We will have a mid-term test in April and a final exam in mid-June.
The grades will be accorded the following weights.
Attendance 10%
Mid-term: 40%
Final: 50%

Homework

Assigned every Tuesday and due to hand in Tuesday the week after.
Last modified: Wed Jul 1 14:13:20 KST 2015