18.218 Probabilistic Method in Combinatorics

Spring 2019, MIT

Class meetings: Tuesdays and Thursdays 2:30–4pm in 3-370

Lecturer: Yufei Zhao (see website for contact info)

Office hours: After lectures or by email appointment. Special office hours will be set up before homework due dates

Course description

A graduate-level introduction to the probabilistic method, a fundamental and powerful technique in combinatorics and theoretical computer science. The essence of the approach is the following: to show that some combinatorial object exists, we prove that a certain random construction works with positive probability. The course will focus on methodology as well as combinatorial applications.

Textbook: Alon and Spencer, The probabilistic method, Wiley (the latest edition is 4th, but earlier editions suffice)

Prerequisites: Mathematical maturity at the level of a first-year math graduate student. Basic knowledge of combinatorics, graph theory, and probability.

Grading: Entirely based on problem sets. No exams.

Student Support Services (S3) and Student Disability Services


Notes taken by Andrew Lin, a student in the class (These note have not been verified or edited by the professor)


Problem set: a list of problems for practice. A subset of these problems will be designated as to-be-turned in by midnight of each due date. You should only submit the designated problems.

Problem set Due date Problems
PS 1 Friday Feb 22 4, 5, 6, 7★, 9, 12, 13(a,b★), 15, 16★
PS 2 Friday Mar 15 21, 22c, 23★, 24★, 26, 28, 30, 31★, 32★, 33★, 34★, 35, 36
PS 3 Friday Apr 5 40, 41, 43, 44★, 45, 46, 47, 48★, 49★, 52(a,b★), 53★, 54(c)★
PS 4 Friday Apr 26 55, 56, 57(a,b★), 58, 59, 60★, 61, 63(a,b★), 64★, 65, 66★
PS 5 Thursday May 16 67–70, (71–75)★, 76, 77★, 80★, 81, 82★, 83★

You are encouraged to submit interesting problem proposals that may be suitable to be included as homework problems for the course (either your own creation or a problem you’ve seen somewhere else). Please submit problem suggestions here.


Submissions. All homework submissions should be typed in LaTeX and submitted as PDF on Stellar. To make the grader’s job easier, please name your file ps#_Lastname_Firstname.pdf (replace # by problem set number, and the rest by your name). Remember to include your name at the top of your submission.

Late policy. Submissions are due on Stellar by midnight of each due date. Late submissions will be penalized by 20% per each late day. For example, for an assignment due on Friday, a submission worth x points if turned in on time will be worth $0.6x$ points if submitted on Sunday.

Sources. At the top of each submission, you must acknowledge all sources and references consulted (other than lectures and the textbook). Failure acknowledge sources will lead to an automatic 10% penalty. Examples include: names of people you discussed homework with, books, and online resources. If you consulted no additional sources, you should write sources consulted: none.

You should not look up solutions to homework problems online (or offline). You are strongly discouraged from looking at end-of-textbook hints unless you have already thought a lot about the problem (at least an hour).

Collaboration policy. You are encouraged to work on the problems first on your own. It is fine to collaborate, but everyone must write their solutions individually and acknowledge their collaborators.