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