Combinatorics for Information Sciences
Contents of the course:
This course provides an introduction to combinatorics and its
many applications in information sciences. 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 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.
Lectures:
Each Friday, 15:15-18:00 in room JK.385, Valckeniersstraat 65 (Roeterseiland).
NB: this room is different from the first three weeks.
The first two hours are lectures ("hoorcollege"), the third hour is to discuss last week's homework, explain things that were unclear, answer questions etc.
Homework, exam, and grading:
There will be homework exercises every week, to be handed in at the start of the next lecture.
Cooperation is allowed, but everyone has to hand in their own solution set in their own words
- English or Dutch. 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 "open book": you can bring your copy of Jukna as well as whatever notes might be useful.
Textbook and prerequisites:
The course will be self-contained, but some prior familiarity with discrete mathematics, (linear) algebra, probability theory, and complexity theory will be very helpful.
Our textbook is:
- S. Jukna, Extremal Combinatorics, with Applications in Computer Science, Springer, 2001.
We will cover selected chapters from this book, at a pace of about one chapter a week.
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.
I will hand out some additional material as well.
Course schedule:
- Sep 8. Introduction and some basic techniques
Book: Prolog/Notation, Chapter 1 up to (incl) Proposition 1.10, Section 2.1
Homework: Exercises 1.4, 1.5, 1.11, 1.18, 1.23
- Sep 15. More advanced techniques
Book: Section 2.1; Chapter 3; Chapter 4, sections 1,2
Homework: 2.5, 2.8, 3.1, 3.2, 4.1, 4.9
- Sep 22. The pigeonhole principle and lower bounds for resolution-based theorem proving
Book: Chapter 4, sections 3,4,8
Homework: 4.3, 4.4, 4.6, 4.13, 4.15
- Sep 29. Systems of distinct representatives and matching
Book: Chapter 5
Homework: 5.2, 5.3, 5.8, 5.9, 5.10
- Oct 6. The sunflower lemma and some lower bounds
Book: Chapter 7
Homework: 7.2, 7.3, 7.6, 7.9, 7.11, 7.12
- Oct 13. Erdos-Ko-Rado theorem, Blocking sets
Book: Section 8.1; Chapter 10, sections 1,2,3,4
Homework: 8.1, 10.1, 10.2, 10.4, 10.7
- Oct 20. Lower bounds for monotone circuits
Book: Chapter 10.6
Homework: 10.5, 10.6, 10.8, 10.12, 10.13
Oct 27. No lecture
- Nov 3. The linear algebra method I
Book: Chapter 14, sections 14.1, 14.2.1, 14.2.2 (Lemma 14.8), 14.3.2
Homework: 14.1, 14.9, 14.15, 14.16, 14.21, 14.23
- Nov 10. The linear algebra method II
Book: Chapter 14, sections 14.2.2 (Theorem 14.7), 14.3.4, 14.5
Homework: 14.4, 14.5, 14.6, 14.17, 14.22, 14.31
- Nov 17. The probabilistic method I
Book: Chapter 17, sections 1,2; Chapter 18, sections 1,2,3,4,5
Homework: 17.1, 17.2, 17.8, 18.3, 18.5, 18.6
- Nov 24. The probabilistic method II
Book: Chapter 20, sections 2,3,5; error-correcting codes
(here is Madhu Sudan's tutorial for some background)
Homework: 20.2, 20.6, 20.9, 20.11, 20.12, 20.13
- Dec 1. The probabilistic method III
Book: Chapter 19, sections 1,3; Chapter 22, sections 1,3
Homework: 19.1, 19.2, 19.3, 22.1, 22.3, 22.4
- Dec 8. Randomized algorithms
Book: Chapter 25, sections 1,2,4; Section 24.1, Schöning's 3-sat algorithm
Homework: 24.2, 25.1, 25.2, 25.3, 25.5
- Dec 15. Communication complexity
Handout
Homework: none
Final exam: Tuesday December 19, 9:30-12:30, P0.14 (Euclides building, Plantage Muidergracht 24).
Since every one who participated in the final exam passed, there won't be
a plenary re-examination.
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.
- Complexity theory:
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Or the more recent (and still free) book by Arora, or the lecture notes of Trevisan.
- 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.
- Communication complexity:
E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, 1997.
- Linear algebra:
R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1990.
Serious questions about the course?
Send e-mail to rdewolf at cwidotnl.
Last update of this page: June 6, 2007.