Lecturer: Ronald de Wolf (CWI)

NB: this room is different from the first three weeks.

The first two hours are lectures ("hoorcollege"), the third hour is to discuss last week's homework, explain things that were unclear, answer questions etc.

- S. Jukna,
*Extremal Combinatorics, with Applications in Computer Science*, Springer, 2001.

- Sep 8. Introduction and some basic techniques

Book: Prolog/Notation, Chapter 1 up to (incl) Proposition 1.10, Section 2.1

Homework: Exercises 1.4, 1.5, 1.11, 1.18, 1.23 - Sep 15. More advanced techniques

Book: Section 2.1; Chapter 3; Chapter 4, sections 1,2

Homework: 2.5, 2.8, 3.1, 3.2, 4.1, 4.9 - Sep 22. The pigeonhole principle and lower bounds for resolution-based theorem proving

Book: Chapter 4, sections 3,4,8

Homework: 4.3, 4.4, 4.6, 4.13, 4.15 - Sep 29. Systems of distinct representatives and matching

Book: Chapter 5

Homework: 5.2, 5.3, 5.8, 5.9, 5.10 - Oct 6. The sunflower lemma and some lower bounds

Book: Chapter 7

Homework: 7.2, 7.3, 7.6, 7.9, 7.11, 7.12 - Oct 13. Erdos-Ko-Rado theorem, Blocking sets

Book: Section 8.1; Chapter 10, sections 1,2,3,4

Homework: 8.1, 10.1, 10.2, 10.4, 10.7 - Oct 20. Lower bounds for monotone circuits

Book: Chapter 10.6

Homework: 10.5, 10.6, 10.8, 10.12, 10.13

Oct 27. No lecture

- Nov 3. The linear algebra method I

Book: Chapter 14, sections 14.1, 14.2.1, 14.2.2 (Lemma 14.8), 14.3.2

Homework: 14.1, 14.9, 14.15, 14.16, 14.21, 14.23 - Nov 10. The linear algebra method II

Book: Chapter 14, sections 14.2.2 (Theorem 14.7), 14.3.4, 14.5

Homework: 14.4, 14.5, 14.6, 14.17, 14.22, 14.31 - Nov 17. The probabilistic method I

Book: Chapter 17, sections 1,2; Chapter 18, sections 1,2,3,4,5

Homework: 17.1, 17.2, 17.8, 18.3, 18.5, 18.6 - Nov 24. The probabilistic method II

Book: Chapter 20, sections 2,3,5; error-correcting codes (here is Madhu Sudan's tutorial for some background)

Homework: 20.2, 20.6, 20.9, 20.11, 20.12, 20.13 - Dec 1. The probabilistic method III

Book: Chapter 19, sections 1,3; Chapter 22, sections 1,3

Homework: 19.1, 19.2, 19.3, 22.1, 22.3, 22.4 - Dec 8. Randomized algorithms

Book: Chapter 25, sections 1,2,4; Section 24.1, Schöning's 3-sat algorithm

Homework: 24.2, 25.1, 25.2, 25.3, 25.5 - Dec 15. Communication complexity

Handout

Homework: none

Final exam: Tuesday December 19, 9:30-12:30, P0.14 (Euclides building, Plantage Muidergracht 24).

Since every one who participated in the final exam passed, there won't be a plenary re-examination.

- Combinatorics:

J.H. van Lint and R.M. Wilson,*A Course in Combinatorics*, 2nd edition, Cambridge University Press, 2001.

I. Anderson,*Combinatorics of Finite Sets*, Oxford University Press, 1987.

B. Bollobas,*Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability*, Cambridge University Press, 1986. - Graph theory:

B. Bollobas,*Modern Graph Theory*, Springer, 2002. - Complexity theory:

C. Papadimitriou,*Computational Complexity*, Addison-Wesley, 1994.

Or the more recent (and still free) book by Arora, or the lecture notes of Trevisan. - Probabilistic method:

N. Alon and J. Spencer.*The Probabilistic Method*, 2nd edition, Wiley, 2000. - Coding theory:

J.H. van Lint,*Introduction to Coding Theory*, 3rd edition, Springer, 1998. - Information theory:

T. Cover and J. Thomas,*Elements of Information Theory*, Wiley, 1991. - Randomized algorithms:

R. Motwani and P. Raghavan,*Randomized Algorithms*, Cambridge University Press, 1995. - Communication complexity:

E. Kushilevitz and N. Nisan,*Communication Complexity*, Cambridge University Press, 1997. - Linear algebra:

R. Horn and C. Johnson,*Matrix Analysis*, Cambridge University Press, 1990.

Serious questions about the course? Send e-mail to rdewolf at cwidotnl.

Last update of this page: June 6, 2007.