18.226 Probabilistic Methods in Combinatorics

Fall 2022, MIT

[Lecture notes] [Problem set]

Class meetings: Mondays and Wednesdays 2:30–4pm, room 4-370

(First class Wednesday September 7)

Instructor: Yufei Zhao

Graders: Yuan Yao and Anqi Li

Emails and Piazza

Office hours

Course description and policies

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.

Topics:

Textbook: Alon and Spencer, The probabilistic method, Wiley (the latest edition is 4th, but earlier editions suffice). Available electronically from MIT Libraries.

I will also provide my own lecture notes.

Prerequisites: Mathematical maturity at the level of a first-year math graduate student. Comfortable with combinatorics (18.211), probability (18.600), and real analysis (18.100).

Grading: Primarily based on homework grades (no exams). A modifier up to 5 percentage points may be applied (in either direction) in calculating the final grade, at my discretion based on factors such as participation.

Final letter grade cutoffs: Only non-starred problems are considered for the calculations of letter grades other than A and A+.

Grades of A and A+ are awarded at my discretion based on overall performance. Solving a significant number of starred problems is a requirement for grades of A and A+ (please don’t ask me what “a significant number” means).

Note that for MIT students, ± grade modifiers do not count towards the GPA and do not appear on the external transcript.

If you wish to attend lectures, please register as for credit or listener.

Students needing support should consider reaching out to Student Support Services (S3), GradSupport, or Student Disability Services.

Lectures

[Lecture notes]

Homework

Problem set

The problem set will be updated over the course of the semester. I will announce on Canvas when each problem set is complete.

You should only submit the designated problems, but are encouraged to try the rest as well.

Starred problems are generally more challenging.

To get the most out of this course, you are expected to spend a significant amount of time solving these problems. It will be essential to start thinking about these problems early.

Problem set Due date
PS 1 Sun Sep 25
PS 2 Sun Oct 9
PS 3 Sun Oct 23
PS 4 Sun Nov 6
PS 5 Sun Nov 20
PS 6 Sun Dec 11

Starred problems on each problem set should be submitted separately, with an automatic 7-day extension without penalty (and no additional lateness permitted).

Submissions

Late policy

Collaborations

Acknowledging collaborators and sources

It is required to acknowledge your sources (even if you worked independently)

Intentional violations of the above policies may be considered academic dishonesty/misconduct.

Additional resources

Previous version of the class: Spring 2019, Fall 2020.