# 18.218 Probabilistic Method in Combinatorics

**Spring 2019, MIT**

**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^{3}) and Student Disability Services

## Lectures

Notes taken by Andrew Lin, a student in the class (These note have not been verified or edited by the professor)

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

Problem set | Due date | Problems |
---|---|---|

PS 1 | Friday Feb 22 | 4, 5, 6, 7★, 9, 12, 13(a,b★), 15, 16★ |

PS 2 | Friday Mar 15 | 21, 22c, 23★, 24★, 26, 28, 30, 31★, 32★, 33★, 34★, 35, 36 |

PS 3 | Friday Apr 5 | 40, 41, 43, 44★, 45, 46, 47, 48★, 49★, 52(a,b★), 53★, 54(c)★ |

PS 4 | Friday Apr 26 | 55, 56, 57(a,b★), 58, 59, 60★, 61, 63(a,b★), 64★, 65, 66★ |

PS 5 | Thursday May 16 | 67–70, (71–75)★, 76, 77★, 80★, 81, 82★, 83★ |

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.

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