18.218 Probabilistic Method in Combinatorics

Spring 2019, MIT (Link to the most current version of the course)

Class meetings: Tuesdays and Thursdays 2:30–4pm in 3-370

Lecturer: Yufei Zhao (see website for contact info)

Office hours: After lectures or by email appointment. Special office hours will be set up before homework due dates

Course description

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)

Prerequisites: Mathematical maturity at the level of a first-year math graduate student. Basic knowledge of combinatorics, graph theory, and probability.

Grading: Entirely based on problem sets. No exams.

Student Support Services (S³) and Student Disability Services

Lectures

Lecture notes taken by Andrew Lin, a student in the class. These note have not been completed verified by the professor so please use at your own risk.

• 2/5 Introduction to the probabilistic method. Ramsey number lower bounds (union bound, alternation, Lovász Loval Lemma). Sperner’s theorem
• 2/7 Bollobás’s two families theorem. Erdős–Ko–Rado theorem. 2-colorable hypergraphs (property B). Linearity of expectations: sum-free sets.
• 2/12 Linearity of expectations: Ramsey multiplicities, Turán’s theorem, Crossing number inequality, Balancing vectors
• 2/14 Linearity of expectations: deterministically balancing vectors, unbalancing lights, dense sphere packings in high dimensions (reference: Venkatesh)
• 2/19 No lecture (MIT Monday schedule)
• 2/21 Alteration method: dominating sets, Heilbronn triangle problem, high girth and high chromatic number, random greedy coloring (2-coloring hypergraphs)
• 2/26 Second moment method: concentration and thresholds for subgraphs in a random graph
• 2/28 Second moment method: clique number, number of prime divisors (Hardy–Ramanujan, Erdős–Kac), multidimensional Szemerédi theorem in the primes (reference: Fox–Zhao)
• 3/5 Second moment method: distinct sums, Weierstrass approximation theorem. Chernoff bound: discrepancy
• 3/7 Chernoff bound: Counterexample to Hajós conjecture. Local lemma: coloring hypergraphs
• 3/12 Local lemma: proof and algorithm (reference: Moser–Tardos)
• 3/14 Local lemma: large independent sets with structure, directed cycles of lengths divisible by k, linear arboricity conjecture
• 3/19 Local lemma: linear arboricity conjecture lopsided LLL
• 3/21 Local lemma: Latin transversals. Correlation inequalities: Harris-FKG inequality
• 3/26,28 No lectures (MIT Spring break)
• 4/2 Janson’s inequalities: statement and proof, probability that a random graph is triangle-free
• 4/4 Janson’s inequalities: lower tail, chromatic number of $G(n,1/2)$
• 4/9 Martingale concentration: Azuma’s inequality, concentration of chromatic number of dense random graph
• 4/11 Martingale concentration: 4-point concentration of chromatic number of sparse random graphs, application to clique number of random graph
• 4/16 No lecture (Patriot’s day vacation)
• 4/18 Class canceled
• 4/23 Concentration of measure, Johnson–Lindenstrauss Lemma
• 4/25 Talagrand inequality: concentration of convex Lipschitz functions, convex distance, top eigenvalue of a random graph (reference: Tao blog)
• 4/30 Talagrand inequality: certifiable functions, longest increasing subsequence of a random permutation. Entropy method
• 5/2 Entropy method: coin-weighing, Bregman’s theorem, Shearer’s inequality, triangle-intersecting families (references for entropy method: Galvin, Radhakrishnan )
• 5/7 Entropy method: the number of independent sets in a regular graph, Sidorenko’s conjecture for trees (reference: Gowers blog)
• 5/9 More on Sidorenko’s conjecture (reference: MathOverflow). Occupancy method: the number of independent sets in a regular graph (reference: Davies–Jenssen–Perkins–Roberts, Perkins lecture notes)
• 5/14 Occupancy method: further applications to independent sets and colorings
• 5/16 Triangles and equations: a trailer for 18.217 Graph Theory and Additive Combinatorics this fall

Homework

Problem set: 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.

You are encouraged to submit interesting problem proposals that may be suitable to be included as homework problems for the course (either your own creation or a problem you’ve seen somewhere else). Please submit problem suggestions here.

Stellar/Gradebook

Submissions. All homework submissions should be typed in LaTeX and submitted as PDF on Stellar. To make the grader’s job easier, please name your file ps#_Lastname_Firstname.pdf (replace # by problem set number, and the rest by your name). Remember to include your name at the top of your submission.

Late policy. Submissions are due on Stellar by midnight of each due date. Late submissions will be penalized by 20% per each late day. For example, for an assignment due on Friday, a submission worth x points if turned in on time will be worth $0.6x$ points if submitted on Sunday.

Sources. At the top of each submission, you must acknowledge all sources and references consulted (other than lectures and the textbook). Failure acknowledge sources will lead to an automatic 10% penalty. Examples include: names of people you discussed homework with, books, and online resources. If you consulted no additional sources, you should write sources consulted: none.

You should not look up solutions to homework problems online (or offline). You are strongly discouraged from looking at end-of-textbook hints unless you have already thought a lot about the problem (at least an hour).

Collaboration policy. You are encouraged to work on the problems first on your own. It is fine to collaborate, but everyone must write their solutions individually and acknowledge their collaborators.