# 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 (S^{3}) 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`

.

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.