18.226 Probabilistic Methods in Combinatorics

Fall 2020, MIT

Quick links: [Notes] [Homework]

Class meetings: Mondays and Wednesdays 2:30–4pm (lectures will be live and recorded)

Instructor: Yufei Zhao (see website for contact info)

Grader: Sergei Korotkikh

Please include “18.226” in the subject line of your emails

Link to Canvas (including Zoom link; MIT Touchstone authentication required for Zoom, Non-MIT individuals must obtain an MIT account, e.g., through cross-registration, to access the lectures)

Office hours: I will stay in the Zoom session after each lecture for around 30 minutes or until all questions have been addressed.

My policy is to not answer by email any math questions related to the class, due to time constraints and also that emails are not a great medium for such Q&As (ask them during office hours instead). Clarification questions (about homework or lectures) should be asked in the Piazza forum (link in Canvas), as they may benefit the rest of the class.

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.

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

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.

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, in particular, solving a significant number of starred problems (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.

Student Support Services (S3) and Student Disability Services

Lectures and notes

Instructor notes (will be updated after each lecture)

Handwritten notes (updated live during lecture)

Notes from a previous semester taken by Andrew Lin (may not perfectly align with this semester, but will be largely similar)

Schedule tentative

Homework

Problem set: a list of problems for practice. A subset of these problems will be assigned as homework. You should only submit the designated problems, but are encouraged to try the rest as well.

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.

Schedule (tentative)

Problem set Due date
PS 1 Sunday Sep 20
PS 2 Sunday Oct 4
PS 3 Sunday Oct 18
PS 4 Sunday Nov 1
PS 5 Sunday Nov 15
PS 6 Wed Dec 9 (9PM)

Submissions

Late policy

Sources

Collaboration policy

Previous course homepage from Spring 2019 (also MIT OCW)