Exploring Combinatorics, Spring 2013

Pigeons and the Ramsey tree
Ramsey number R(4,3)≤10
© 2013 Laure Bukh
Used with permission


Mondays, Wednesdays, Fridays 9:30


Margaret Morrison Carnegie Hall, room A14


Combinatorics is an area of mathematics that deals with finite objects. Finite sets, permutations, relations, partitions, graphs, and trees …. These simple combinatorial objects can be used to express beautiful mathematical ideas with little technical work. The ideas that we explore in this course fall into three broad classes:

  1. Counting. We will enjoy the transparency of combinatorial bijections, and learn to craft mindless but powerful proofs via generating functions. We will take the idea of counting “all but” to the extreme, and use the resulting principle of inclusion-exclusion to count even the uncountable.
  2. Ramsey theory. The pigeonhole principle is the main tool here. Among its many consequences, Ramsey's theorem is singularly important, and we shall see many applications of both.
  3. Probabilistic method. A remarkable discovery of XXth century mathematics is that probability is useful even where order reigns. We shall see the manifestation of this great idea in combinatorics; we will use it to construct objects with most unlikely properties.

On the way, we will learn cheerful miscellanea about graphs, permutations, prime numbers, and rabbits.


The main text for the course is Invitation to Discrete Mathematics by Jiří Matoušek and Jaroslav Nešetřil, 2nd ed. We will occasionally cover topics that are not in the book. Links to additional resources will be posted as the course progresses.

More fun:

More fun can be had at my office hours on Mondays 10:30–11:20am, and Thursdays 11:00–11:50 and 2:30–3:20pm in Wean 6202. I am also available by appointment.

Course activities:

Mastery of combinatorics requires practice. Hence, there will be regular homeworks. Since the homework is for your practice, you are advised to do homework individually. However, collaboration is permitted. Collaboration may involve only discussion, all the writing must be done individually.

Students are expected to fully participate in the class. Discussions during the lectures are encouraged.

The homework will count for 25% of the grade. During the semester there will be three tests (on February 6, March 20, and April 24). The lowest test score will be dropped, and the two remaining scores will contribute 25% each. The final exam will take place on May 13 and will count for 25% of the grade.


Book sections covered (as of May 3): 2.1–2.3, 3.1–3.8, 7.2–7.3, 9.1–9.4, 10.1–10.4, 11.1–11.3, 12.1–12.4, and parts of 2.4 and 12.7.
Some topics were covered at a greater depth in the lecture than in the textbook, and we covered some topics not in the book.

Back to the homepage