Discrete Mathematics Two DMAT UM0

Fall 2013


Andrzej Ruciński

Syllabus

DateTopicComments
7 X Lecture 1: Systems of distinct representatives ...
8 X Lecture 2: Systems of distinct representatives (cont.)

Problem set 1

14 XExercises: Problem set 1. ...
15 X Exercises: Problem set 1 (cont.) and Lecture 3: Sperner Systems and the LYM inequality.

Problem set 2

21 XExercises: Problem set 2. ...
22 X Exercises: Problem set 2 (cont.) and Lecture 4: The Littlewood-Offord problem. Dilworth's Theorem.

Problem set 3

28 XExercises: Problem set 3. ...
29 X Exercises: Problem set 3 (cont.) and Lecture 5: The Erdos-Ko-Rado Theorem on intersecting hypergraphs.

Problem set 4

4 XIExercises: Problem set 4. ...
5 XI Exercises: Problem set 4 (cont.) and Lecture 6: The Erdos-Ko-Rado Theorem -- proofs using shadows. Shifting.

Problem set 5

12 XIExercises: Problem set 5. Lecture: Proof of E-K-R via shifting. No homework this week!
18 XILecture 7: Matchings in k-graphs. The Erdos Conjecture.
19 XI Lecture 7 (cont.): Frankl Theorem on Erdos Conjecture.

Problem set 6

25 XIExercises: Problem set 6.
26 XI Lecture 8: The Aharoni proof of Ryser conjecture for r=3.

Problem set 7

2 XIIExercises: Problem set 7.
3 XIExercises: Problem set 7 (cont.)
9 XIIExercises: Problem set 7 (to finish). Lecture 9: Ramsey Theorem.
10 XIILecture 10: Ramsey Theorem (cont.).

Problem set 8

12 XIILecture 11: Schur Theorem and Van der Waerden Theorem3:30 PM, moved from January 20
16 XIIMidterm Review
17 XIIMidterm Test Results
19 XIIExercises: Problem set 8 3:30 PM, moved from January 21
7 ILecture 12: Van der Waerden Theorem and Hales-Jewitt Theorem
10 ILecture 13: The Game of Set. The Shelah proof.11:30 AM, moved from January 27
13 ILecture 14: The Shelah proof. The Szemeredi Theorem.

Problem set 9

14 ILecture 15: The Szemeredi Theorem.
17 IExercises: Problem Set 911:30 AM, moved from January 28
27 IThe Final Exam8:20-9:55, room A2-24