Combinatorics with computer science applications, UvA course code 5314CWCS6Y
February-March 2014

Lecturer: Ronald de Wolf (CWI and ILLC)

Contents of the course:

This course provides an applied introduction to combinatorics. Combinatorics is the art of counting and analyzing discrete structures with various properties, such as graphs, systems of sets, matrices, algorithms, etc. It is the main branch of mathematics that one uses in theoretical computer science and related fields, and is full of beautiful techniques and results. Among the applications, we will describe a number of interesting and efficient algorithms, and analyze the limitations of computational systems such as Boolean circuits. The course will be self-contained, though some prior familiarity with discrete mathematics, probability theory, linear algebra, and computational complexity theory will be helpful.

Here is a related, more math-oriented course taught by Ross J. Kang and Tobias Müller in Fall'13 in Utrecht.

Textbook:

We will cover selected chapters from this book, at a pace of about one chapter per lecture. Combinatorics is broad rather than deep, which allows us to deal with a new topic each lecture in a reasonably self-contained way.

Homework, exam, and grading:

This is a 6-credit course spread over 7 weeks of lectures, which comes to roughly 20 hours of work per week. There will be homework exercises every week, to be handed in before or at the start of the next Friday lecture. The answers should be in English. You can hand it in on paper, or email a readable file to rdewolf at cwi dot nl. Cooperation is allowed, but everyone has to hand in their own solution set in their own words. Each homework set will get a grade between 1 and 10; if you don't hand it in you'll score a 1 for that week. When determining the average grade for the homework I will ignore your lowest score. This is supposed to handle also cases of illness, forgetfulness etc, so it's pointless to ask for exceptions or special treatment when you're late. The final exam on March 29 is open book, meaning you can bring the book and whatever notes you have, but no electronic devices. The overall grade will be determined 40-60 by the homework and the final exam.

Course schedule:

February 5 - Mar 21, 2014, Wednesdays 15.00-19.00 in SP A1.14 and Fridays 11.00-13.00 in SP A1.06.
  1. [Feb 5] Introduction and some basic counting techniques
    Book: Preface/Notation. Chapter 1.1, 1.4, 4.3
    Homework (to be handed in Feb 7): Exercises 1.2, 1.5, 1.9, 1.10, 1.12, 1.13
  2. [Feb 7] 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 14): Exercises 1.21, 1.32, 1.33, 2.1
  3. [Feb 12] 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 14): Exercises 4.4, 4.5, 4.11, 4.14, 4.16
  4. [Feb 14] Systems of distinct representatives and algorithms for matching
    Book: Chapter 5, except 5.2.1
    Homework (to be handed in Feb 21): Exercises 5.1, 5.6, 5.8, 5.9
  5. [Feb 19] Sunflowers
    Book: Chapter 6.1, 6.2.2, 6.3.2
    Homework (to be handed in Feb 21): Exercises 6.2, 6.3, 6.6, 6.11, 6.12
  6. [Feb 21] 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, 8.4, 8.5, 8.10
  7. [Feb 26] 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]
  8. [Feb 28] The linear algebra method
    Book: Chapter 13.1, 13.3, 13.6
    Homework (to be handed in Mar 7): 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]
  9. [Mar 5] The probabilistic method I
    Book: Chapter 3.1, 3.2, 18.1, 18.7
    Homework (to be handed in Mar 7): Exercises 3.5, 3.10, 3.11, 3.12
  10. [Mar 7] 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 14): Exercises 3.3, 17.2, 17.7, 18.9, 18.14
  11. [Mar 12] Randomized algorithms, random walks
    Book: Chapter 16.1 and 23.1
    Homework (to be handed in Mar 14): Exercises 16.2, 16.3, 16.4, 23.1
  12. [Mar 14] Expander graphs
    Book: Chapter 15.1, 15.2 and 23.3
    Homework (to be handed in Mar 21): Exercises 15.1, 15.2, 15.4, 15.5 [additonal hint: write the trace of A^2 in two different ways]
  13. [Mar 19] Hereditary sets and matroids
    Book: Chapter 10.1, 10.2 and 10.3
    Homework (to be handed in Mar 21): Exercises 10.1, 10.10, 10.11, 10.12, 10.13
  14. [Mar 21] Communication complexity
    Instead of the book: this introduction to communication complexity
    No homework, but probably one exam-question will be about communication complexity

    [Mar 29] final exam 10.30-13.30 in SP A1.06.
    NB: this is a *Saturday*, not the earlier-planned Friday (to prevent overlap with another exam)

    [Apr 12] re-sit of the exam 10.30-13.30 in SP A1.06.

    If you want to practice: here and here are two old exams
Last update of this page: April 8, 2014.