Teaching assistant: Giannicola Scarpa (CWI)

- Stasys Jukna,
*Extremal Combinatorics, with Applications in Computer Science*, 2nd edition, Springer, 2011.

At the time of writing this costs around 60 Euros at amazon.de and around 60 Pounds at amazon.co.uk.

Chapters can also be downloaded from the UvA library.

Location:

- [Feb 9] Introduction and some basic counting techniques

Book: Preface/Notation. Chapter 1.1, 1.4, 4.3

Homework: Exercises 1.2, 1.5, 1.9, 1.10, 1.14, 1.15 - [Feb 16] More advanced counting

Book: Chapter 1.2, 1.6, 2.6 [NB: equation 2.7 should be in the other direction]

Homework: Exercises 1.13, 1.21, 1.32, 1.33, 1.36, 2.1 - [Feb 23] The pigeonhole principle

Book: Chapter 4.1, 4.2, 4.4, and the lower bound for resolution

Homework: Exercises 4.1, 4.4, 4.5, 4.7, 4.11, 4.20 - [Mar 1] Systems of distinct representatives and algorithms for matching

Book: Chapter 5, except 5.2.1

Homework: Exercises 5.1, 5.4, 5.6, 5.8, 5.9, 5.10 - [Mar 8] Sunflowers

Book: Chapter 6.1, 6.2.2, 6.3.2

Homework: Exercises 6.2, 6.3, 6.6, 6.8, 6.11, 6.12 - [Mar 15] Chains and antichains

Book: Chapter 8.1, 8.3, 8.6, and Sections 1 and 2 of this application to data structures

Homework: Exercises 8.1, 8.4, 8.5, 8.6, 8.8, 8.10 - [Mar 22] Blocking sets

Book: Chapter 9.1, 9.2, 9.4

Homework: Exercises 9.2, 9.6, 9.7, 9.8, 9.9 [insert "at least" after "depth"]

[Mar 29] midterm exam 13.00-16.00 in G2.13 [NB: different time and room than the lectures]

- [Apr 5] The linear algebra method

Book: Chapter 13.1, 13.3, 13.6

Homework: Exercises 13.1, 13.9, 13.10, 13.17 [page 196, line 4: the mu_j indices should be mu_{I_j}, and order the |I_j| from small to large], 13.18 - [Apr 12] The probabilistic method I

Book: Chapter 3.1, 3.2, 3.3, 18.1, 18.7

Homework: Exercises 3.1, 3.6, 3.10, 3.11, 18.14 [assume here that k>3] - [Apr 19] The probabilistic method II

Book: Chapter 18.11, 21.1, 21.5, and Section 3 of this application to data structures

Homework: Exercises 3.3, 3.5, 18.9, 18.11, 21.8, 21.9 - [Apr 26] Randomized algorithms, random walks

Book: Chapter 16.1 and 23.1

Homework: Exercises 16.2, 16.3, 16.4, 16.6, 16.7 [read "How large must N be" as "How large an N suffices"; ignore the last 4 words of the hint] - [May 3] Expander graphs

Book: Chapter 15.1, 15.2 and 23.3

Homework: Exercises 15.1, 15.2, 15.4, 15.5 [additonal hint: write the trace of A^2 in two different ways], 15.6 [if you use Ex 13.21 here, so you should prove that too] - [May 10] Information theory

Book: Chapter 22

Homework: Exercises 22.2, 22.3, 22.4, 22.5, 22.6, 22.8, 22.9

[May 17] no class

- [May 24] Communication complexity

Book: this introduction to communication complexity

No homework, but probably one exam-question will be about communication complexity

[May 30] final exam 13.00-16.00 in G4.15 [NB: different day, time, and room than the lectures]

Last update of this page: May 24, 2012.