Combinatorics with computer science applications
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 like resolution-based theorem proving and 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.
Lectures:
Starting February 7, 2008:
every Thursday, 15:45-17:30, Room 401.
Homework, exam, and grading:
There will be homework exercises every week, to be handed in at or before the start of the next lecture.
You can hand it in on paper, or email me a readable file (rdewolf at cwidotnl; no .doc files please),
or fax to 020-5924312 (from abroad: +31 20 5924312).
Cooperation is allowed, but everyone has to hand in their own solution set in their own words
- English or Dutch.
I will usually devote the last 10 minutes of each week to discussing the previous homework.
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 two lowest scores.
The final grade is determined 50-50 by the average homework-grade and the final exam (there is no mid-term exam).
The final exam is at: Thursday, May 22, 14:00-17:00, Room 403.
It is "open book": you can bring your copy of Jukna as well as whatever notes might be useful.
Textbook:
- S. Jukna, Extremal Combinatorics, with Applications in Computer Science, Springer, 2001.
The author maintains a website about the book.
I recommend you print his list of errata and keep it with the book to avoid being confused by some small errors.
We will cover selected chapters from this book, at a pace of about one chapter a week.
Combinatorics is broad rather than deep, which allows us to deal with a new topic each week
in a reasonably self-contained way.
Course schedule:
- [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.
Further reading:
If you want to read more about...
- 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.