February-March 2016

Teaching assistant: Srinivasan Arunachalam (CWI)

Here is a related, more math-oriented course taught by Ross J. Kang and Tobias Müller in Fall'15 at the Free University.

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

Chapters can also be downloaded from the UvA library.

- [Feb 2] Introduction and some basic counting techniques

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

Homework (to be handed in Feb 5): Exercises 1.2, 1.5, 1.9, 1.10, 1.12, 1.13

- [Feb 5] More advanced counting

Book: Chapter 1.2, 1.6, 2.6 [only Lovasz-Stein. NB: equation 2.7 should be reversed]

Homework (to be handed in Feb 12): Exercises 1.21, 1.32, 1.33, 2.1

- [Feb 9] The pigeonhole principle

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

Homework (to be handed in Feb 12): Exercises 4.4, 4.5, 4.11, 4.14, 4.16

- [Feb 12] Systems of distinct representatives and algorithms for matching

Book: Chapter 5, except 5.2.1

Homework (to be handed in Feb 19): Exercises 5.1, 5.6, 5.8, 5.9

- [Feb 16] Sunflowers

Book: Chapter 6.1, 6.2.2, 6.3.2

Homework (to be handed in Feb 19): Exercises 6.2, 6.3, 6.6, 6.11

- [Feb 19] Chains and antichains

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

Homework (to be handed in Feb 28): Exercises 8.1 [n is the universe size here], 8.4, 8.5, 8.10

- [Feb 23] Blocking sets

Book: Chapter 9.1, 9.2, 9.4

Homework (to be handed in Feb 28): Exercises 9.2, 9.6, 9.7, 9.9 [NB: you need to prove a lower bound of m^2]

- [Feb 26] The linear algebra method

Book: Chapter 13.1, 13.3, 13.6

Homework (to be handed in Mar 4): 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]

- [Mar 1] The probabilistic method I

Book: Chapter 3.1, 3.2, 18.1, 18.7

Homework (to be handed in Mar 4): Exercises 3.5, 3.10, 3.11, 3.12

- [Mar 4] The probabilistic method II

Book: Chapter 3.3, 17.3, 18.11, and Section 3 of this application to data structures

Homework (to be handed in Mar 11): Exercises 3.3, 17.5, 17.7, 18.9, 18.14

- [Mar 8] Randomized algorithms, random walks

Book: Chapter 16.1 and 23.1

Homework (to be handed in Mar 11): Exercises 16.2, 16.3, 16.4, 23.1

- [Mar 11] Expander graphs

Book: Chapter 15.1, 15.2 and 23.3

Homework (to be handed in Mar 18): Exercises 15.1, 15.2, 15.4, 15.5 [additonal hint: write the trace of A^2 in two different ways]

- [Mar 15] Elective topic 1: Hereditary sets and matroids

Book: Chapter 10.1, 10.2, 10.3

Homework (to be handed in Mar 18): Exercises 10.1, 10.10, 10.11, 10.12, 10.13 [in 10.11 "all independent subsets of Y" should be "all maximal independent subsets of Y"; in 10.12 assume k>1]

- [Mar 18] Elective topic 2: Information theory

Book: Chapter 22

No homework for this lecture, but probably one exam-question will be about information theory

[Mar 24] final exam 13.00-16.00 in SP G4.15

If you want to practice: here and here are two old exams

Last update of this page: March 17, 2016.