18.226 Probabilistic Methods in Combinatorics

Fall 2020, MIT (Link to the most current version of the course)

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)

Unfortunately, due to MIT policies, I cannot release lecture videos to anyone outside MIT. All the publicly accessible material from the course are already contained on this page.

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+:

• A− : ≥ 85%
• B− : ≥ 70%
• C− : ≥ 50%

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 (S³) and Student Disability Services

Lectures and notes

Instructor notes (will be updated after each lecture; report errors)

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

• 9/2 Introduction
• 9/9 Introduction
• 9/14 Linearity of expectations
• 9/16 Linearity of expectations
• 9/21 Alteration method
• 9/23 Alteration method / Second moment method
• 9/28 Second moment method
• 9/30 Thresholds
• 10/5 Second moment method
• 10/7 Chernoff bound
• 10/13 Lovász local lemma
• 10/14 Lovász local lemma
• 10/19 Lovász local lemma
• 10/21 Correlation inequalities
• 10/26 Janson inequalities
• 10/28 Janson inequalities
• 11/2 Martingale concentration
• 11/4 Martingale concentration
• 11/9 Isoperimetric inequalities
• 11/16 Talagrand inequality
• 11/18 Talagrand inequality
• 11/30 Entropy method
• 12/2 Entropy method
• 12/7 Entropy method
• 12/9 Container method

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

Submissions

• Must be typed in LaTeX and submitted as PDF on Gradescope (accessed from Canvas).
• Due time: 11:59pm of each due date (except for PS 6, which is due at 10 PM). All times refer to US Eastern time
• Begin each solution on a new page
• Each box on the left-margin of the problem set PDF indicates a single problem worth 10 points

Late policy

• Penalty. Late submissions will be penalized by 20% per each late day (24-hour increments, without fractional accounting).
  • Example: for an assignment due on Sunday, a submission worth x points if turned in on time will be worth 0.6x points if submitted on Tuesday.
• Multiple submissions. You are allowed to submit some of the problems on time and some of the problems in a separate “late” batch and have the late penalty applied only to the late batch.
  • You are allowed to submit at most two batches (i.e., 1 ontime + 1 late batch, or 2 separate late batches)
  • The second batch may not contain any updates or replacement to an already submitted problem.
  • The final submission should include everything, with the late problems clearly marked.
  • Please email me and the graders if you submit in two batches, with details on which problems are submitted in which batch, as multiple submissions complicate our grading process.
  • This policy is provided as a courtesy; it may be rescinded if subject to abuse.
• Extensions. If you need an extension for valid excuses (e.g., unanticipated health or family issues), please email me in advance or have S3 send me a message.
  • My policy is to not grant extension based on forseeable circumstances including other academic workload, extracurriculars, and poor study habits.

Sources

• Important! Please acknowledge, individually for every problem at the beginning of each solution, a list of all collaborators and sources consulted (people, books, websites, etc.).
• If no additional sources are consulted, you must write sources consulted: none or equivalent.
• Failure to acknowledge sources will lead to an automatic 1 point penalty (out of 10 points per problem).
• You may not look up solutions to homework problems online or offline.
• You are strongly discouraged from looking at end-of-textbook hints.

Collaboration policy

• Start early and first think about the problems independently; you will gain the most of out the course this way.
• Reasonable collaboration is permitted, but everyone must write their solutions individually and acknowledge their collaborators.
• Pset partners — tool for finding problem set collaborators (MIT Touchstone required)