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

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 on Piazza (link in Canvas), as they may benefit the rest of the class. The same goes for other discussions of general interest. Do not discuss hints or solutions to homework problems on Piazza until after the due date.
Email the graders and cc me for anything homework-related (submission, extensions, grading, etc.)
Begin your email subject line with “[18.226]”

Office hours

I will stay around after class to answer questions – we may move to the math common room (2-290).
I plan to also schedule ad-hoc office hours for each problem set. Stay tuned for Canvas announcements.
You may ask me about unstarred problems (but not starred ones) during office hours.
I will ask you to first explain on the board the progress you have made so far.

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

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

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 (S³), GradSupport, or Student Disability Services.

Lectures

[Lecture notes]

9/7 Introduction
9/12 Introduction
9/14 Linearity of expectations
9/19 Linearity of expectations
9/21 Alterations
9/26 Second moment
9/28 Thresholds
10/3 Second moment
10/5 Chernoff bound
10/10 Holiday. No class
10/12 Lovász local lemma
10/17 Lovász local lemma
10/19 Special lecture by Joel Spencer
10/24 Lovász local lemma
10/26 Lovász local lemma
10/31 Correlation inequalities
11/2 Janson inequalities
11/7 Janson inequalities
11/9 Concentration of measure
11/14 Concentration of measure
11/16 Concentration of measure
11/21 Concentration of measure
11/23 Class canceled
11/28 Concentration of measure
11/30 Concentration of measure
12/5 Entropy method
12/7 Entropy method
12/12 Entropy method
12/14 Container method

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

Must be typed in LaTeX and submitted as PDF on Gradescope (accessed from Canvas).
Due time: 11:59pm of each due date
Begin each solution on a new page
Select the pages for each problem on Gradescope (or else they will not be graded)
Each box on the left-margin of the problem set PDF indicates a single problem worth 10 points
Regrade requests should be submitted on Gradescope within one week of the grades being published

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.
- If you take this option, you must (1) email the graders explaining which problems were submitted on time and which ones were late and by how many dates, and (2) clearly indicate this information also in your write-up.
- Multiple submissions complicate our grading process. If you do not do the above, your entire submission may receive a late penalty as if all problems were submitted by the last submission time.
- 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 each problem’s lateness clearly marked in the PDF.
- This policy is provided as a courtesy. It may be rescinded if abused.
Extensions. If you need an extension for valid excuses (e.g., unanticipated health or family issues), please email the graders and me in advance or have S3 send us a message. Let us know how many days extension you need.
- My policy is to not grant extension based on forseeable circumstances including academic workload, extracurriculars, and poor study habits.
If you submit your homework late, you should not discuss the homework with other students who have already submitted their homework until you have submitted yourself (this includes reading Piazza discussions).

Collaborations

You are encouraged to first work on the homework problems independently before seeking collaboration.
Meaningful collaboration is allowed if it helps with your learning (e.g., solving a problem together)
Unacceptable practices include: “dividing up” the problems among a group and then distributing the solutions; asking for a solution from a friend.
You must write up your own solutions.
Pset partners — a tool for finding problem set collaborators (MIT Touchstone required)

Acknowledging collaborators and sources

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

At the beginning of the submission for each problem, write Collaborators and sources: followed by a list of collaborators and sources consulted (people, books, papers, websites, software, etc.), or write none if you did not use any such resources.
Failure to acknowledge will result in an automatic 1pt penalty per problem.
Acceptable uses of resources include: looking up a standard theorem/formula/technique; using Wolfram Alpha/Mathematica/Python for a calculation (no need to mention lecture notes or textbook)
Unacceptable uses of resources include: directly looking up the problem online or in the research literature for a solution. (Once you have solved a problem, it is fine to seek and learn alternate solutions.)

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

Additional resources

MIT-Harvard-MSR Combinatorics Seminar – research seminar covering recent research results by various speakers. Intended for graduate students and researchers in combinatorics, but all are welcome. Self-sign up for mailing list.

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