18.226 Probabilistic Methods in Combinatorics

Fall 2020, MIT

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

Instructor: Yufei Zhao (see website for contact info)

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

Link to Canvas (including Zoom link; MIT Touchstone authentication required for Zoom)

Office hours: I still 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 Canvas forum, 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, the discretion of the instructor based on factors such as general participation.

Cutoffs: Only non-starred problems are considered for the calculations of the letter grades other than A or 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).

Student Support Services (S³) and Student Disability Services

Lectures

Schedule tentative

• 9/2 Introduction to the probabilistic method.
• 9/9 Linearity of expectations
• 9/14 Linearity of expectations
• 9/16 Alteration method
• 9/21 Alteration method
• 9/23 Second moment method
• 9/28 Second moment method
• 9/30 Chernoff bound
• 10/5 Local lemma
• 10/7 Local lemma
• 10/13 Local lemma
• 10/14 Correlation inequalities
• 10/19 Janson’s inequalities
• 10/21 Janson’s inequalities
• 10/26 Martingale concentration
• 10/28 Martingale concentration
• 11/2 Concentration of measure
• 11/4 Talagrand inequality
• 11/9 Talagrand inequality
• 11/16 Entropy method
• 11/18 Entropy method
• 11/30
• 12/2
• 12/7
• 12/9

Lecture notes taken by Andrew Lin, a student in a previous version of the course, are available here. They are NOT the official notes of the this course. They may contain inaccuracies, and may not align with the contents of the current version of the course.

Homework

Problem set (to be posted): 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.

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

Submissions

• Must be typed in LaTeX and submitted as PDF on 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

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 submission. 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.
  • 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 1pt penalty. 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.

Previous course homepage from Spring 2019 (also MIT OCW)