Combinatorics has had many strong connections with computer science as well as almost all other branches of natural sciences. These days courses on combinatorics are an integral part of CS curricula both at the graduate and undergraduate levels at many universities. In this course we will focus on a field of combinatorics known as Extremal Combinatorics, that has undergone a period of spectacular growth in recent decades. Roughly, in this field of combinatorics one studies problems that can be phrased generically as: if a collection of finite objects (numbers, graphs, vectors, sets, etc.) satisfies certain constraints, then how large or how small can it be?
For a concrete example consider this problem: How many people can we invite to a party where among each three people there are two who know each other and two who do not know each other? Recently one of the greatest names in this field
Endre Szemeredi was honored for his work by the prestigious Abel Prize. The techniques in extremal combinatorics have found many applications in computer science from circuit complexity to expanders and error-correcting codes, to k-SAT problem, derandomization, communication complexity, etc.
This will be a first course in extremal combinatorics. No prior knowledge in combinatorics is required, although it will undoubtedly be useful to know somethings. I will assume mathematical maturity and willingness to think about problems that range from easy to difficult. We will cover basic tools of combinatorics, extremal set theory, linear algebraic method and probabilistic method, time permitting we might venture into the fascinating new research area of additive combinatorics.
Mathematical maturity, and willingness to think about, and work on problems.
- Advanced Counting
- The Pigeonhole Principle
- Extremal Set Theory
- Linear Algebraic Method
- Probabilistic Method
- Applications in Theoretical Computer Science
There is no single textbook for the course, however I will draw heavily from the following books:
- Extremal Combinatorics with Applications in Computer Science, second edition, Stasys Jukna
- Modern Graph Theory, Bela Bollobas, Springer Graduate Textx in Mathematics, Springer-Verlag, 1998.
- Additive Combinatorics, Terrence Tao and Van Vu, Cambridge Studies in Advanced Mathematics,
Handouts and Homework:
All handouts and homework assignments will be posted on Oncourse.
- Homework assignments: 50%
- There will be a few homework assignments (at most 6).
- Solutions must be written LEGIBLY.
- It is encouraged to discuss the problem sets with
others, but everyone needs to turn in a unique personal
- Midterm Exam: 20%
- Final Take-home Exam: 30%
- Collaborative work:
One of the best ways to learn new material is to collaborate in groups.
You may discuss the homework problems with your classmates, and in this way
make the learning process more enjoyable. However, the homework you hand in must be
your own work, in your own words and your own explanation. As for projects completed by groups, the contributions
of each member must be clearly explained on a separate page.
- Here is the link to
of Student Conduct.