Lecturer: Ronald de Wolf (CWI)

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

- [Feb 7] Introduction and some basic counting techniques.

I will explain Turan's Theorem (Chapter 4.4) and equality-testing of long strings (Chapter 25.2) to illustrate the kind of topics this course is about, and then start with Chapter 1.

Book: Preface/Prolog/Notation. Chapter 1, sections 1-4.

Homework: Exercises 1.2, 1.4, 1.5, 1.10, 1.23 - [Feb 14] More advanced techniques: Inclusion-exclusion and the pigeonhole principle.

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

Homework: Exercises 3.2, 3.3, 4.1, 4.3, 4.4, 4.13 - [Feb 21] Lower bound for resolution-based proofs of the pigeonhole principle.

Book: Chapter 4, sections 5 and 8

Homework: Exercises 4.5, 4.11, 4.14, 4.15 [in 4.14: assume that leaves have weight 1] - [Feb 28] Systems of distinct representatives.

Book: Chapter 5, sections 1, 2, 3

Homework: Exercises 5.2, 5.3, 5.5, 5.10 - [Mar 6] Algorithms for matching. The Erdös-Ko-Rado theorem.

Book: Chapter 5, section 4; Chapter 8, section 1

Homework: Exercises 5.6, 5.9, 8.1, 8.2, 8.3 - [Mar 13] The sunflower lemma.

Book: Chapter 7

Homework: Exercises 7.2, 7.3, 7.4, 7.6, 7.9, 7.11 - [Mar 20] Blocking sets.

Book: Chapter 10, sections 1, 4

Homework: Exercises 10.1, 10.2, 10.5, 10.7, 10.8, 10.12

[Mar 27] no lecture

- [Apr 3] The linear algebra method.

Book: Chapter 14, sections 14.1, 14.3.2, 14.3.4. Read through Theorem 14.7 and section 14.4.1

Homework: Exercises 14.4, 14.21, 14.22, 14.23, 14.31 - [Apr 10] The probabilistic method I (the union bound).

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

Homework: Exercises 17.1, 17.5, 18.3, 18.5, 18.6 - [Apr 17] The probabilistic method II (Lovász local lemma, and linearity of expectation).

Book: Chapter 19, section 1, and Theorems 19.4 and 19.5; Chapter 20, sections 2, 3

Homework: Exercises 19.1, 19.2, 19.3, 20.2, 20.6, 20.9 - [Apr 24] Circuit lower bounds.

Book: Lemma 14.8 and Chapter 20, section 5

Homework: Exercises 14.15, 14.16, 14.17, 17.2, 20.10

[May 1] no lecture

- [May 8] Information theory methods.

Book: Chapter 23. I will also do Shannon's noiseless coding theorem, which is not in the book.

Homework: Exercises 23.2, 23.3, 23.6, 23.8, 23.9 - [May 15] Randomized algorithms.

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

No homework

Final exam: Thursday, May 22, 14:00-17:00, Room 403.

- 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.

R. Diestel,*Graph Theory*, Springer, 2005. Available for free online here. - 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. - Complexity theory:

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

Or the more recent (and still free) book by Arora and Barak, or the lecture notes of Trevisan.

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

Last update of this page: April 18, 2008.