# 18.218 Probabilistic Method in Combinatorics

Spring 2019, MIT

Class meetings: Tuesdays and Thursdays 2:30–4pm in 3-370 (note room number!)

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

## Lectures

• 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 Ramsey multiplicities. Turán’s theorem. Crossing number inequality. Balancing vectors
• 2/14 Deterministically balancing vectors. Unbalancing lights. Dense sphere packings in high dimensions (reference: Venkatesh)
• 2/19 No lecture (MIT Monday schedule)
• 2/21 Alteration method …
• 2/26
• 2/28

## 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
PS 3 Friday Apr 5
PS 4 Friday Apr 26
PS 5 Thursday May 16

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.