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

Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistant: Srinivasan Arunachalam (CWI)

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'15 at the Free University.

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 Srinivasan (arunacha at cwi dot nl) with cc to Ronald (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 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 2 - March 18: Tuesdays 15.00-18.00 in SP G0.05 and Fridays 9.00-12.00 in SP G0.05.
  1. [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

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

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

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

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

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

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

  8. [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]

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

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

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

  12. [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]

  13. [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]

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