For 18.447, we will be using the textbook Alon and Spencer, The
Probabilistic Method. I will be trying to use examples both from
combinatorics and algorithms, but the emphasis will likely be on
combinatorics, since this is the emphasis in the book. I haven't taught
this course before, so I don't know exactly how much material I will
end up covering, but my current plan is to cover at least the basic
probabilistic method (selections from chapters 1-3), the second moment
method (chapter 4), the Lovasz local lemma (chapter 5), martingales
(chapter 7), and random graphs (chapter 10).
I will give one takehome midterm, on Tuesday Oct. 26.
There are homework assignments, and a final project.
Homework assignments will be given roughly every two weeks.
The first homework assignment is to do Problems 1, 8, and 10
from Chapter 1, and Problems 2 and 7 from Chapter 2, of Alon and Spencer.
Hint for problem 2. Consider the real line modulo r, for real numbers r.
(This is a hint for the way I know to solve it ... there may be other
solutions as well.)
The second homework is to do Problem 1 from Chapter 3, Problem 1 from
Chapter 15, and Problems 1,4, and 5 from Chapter 4.
The third homework is
here. I was wrong about the second problem; you can actually
use the symmetric version of the Lovasz Local Lemma if you find
the right (and not particularly difficult) clever trick.
The midterm is
Note that a typo has been corrected in problem 2.
The fifth homework is chapter 6, problem 1 and chapter 10, problems 1 and 3.
It will be due Thursday, Nov. 18.
I will try to announce the chapters of Alon and Spencer that
contain the material we're covering here. I'm not following
the book exactly, so I will skip over some material from these
chapters, and may include some extra material, but for those who
want to look at the textbook before class, this will give an
idea of what I'll be covering.
Thur. 09/09: Introduction; chapter 1
Tue. 09/14: To be added later.
Thur. 09/16: Coding Theory. Sections 14.1, 3.4, and the
Tue. 09/21: We covered two topics that I found on-line;
section 2.1 of these
notes and Section 2 of
Thur. 09/23: We'll talk about Chernov bounds, and an
application of them.
Tue. 09/28: Second moment method, 4.1 - 4.4
Thur. 09/30: Second moment method continued
Tue. 10/05: Lovasz Local Lemma 5.1, 5.2, 5.3
Thur. 10/07: algorithmic Lovasz Local Lemma section 5.7
Tue. 10/12: Azuma's inequality. (7.1, 7.2, 7.5)
Thur. 10/14: Use of Azuma's inequality for chromatic
Tue. 10/19: Start of Talagrand's inequality. Section 7.6
Thur. 10/24: Finish up Talagrand's inequality.
Tue. 10/26: FKG inequality
Thur. 10/28: FKG inequality: finite distributive lattices
and Shepp's application to linear extensions
of partial orders.
Tue. 11/2: Janson's inequality (chapter 8)
Thur. 11/4: Brun's sieve
Tue. 11/9: random graphs (chapter 10)
Thur. 11/11: HOLIDAY
Tue. 11/16: more on the phase transition in random graphs
Thur. 11/18: expanders
Tue. 11/20: more on expanders
Thur. 11/25: HOLIDAY
Tue. 11/30: Markov chain mixing and conductance. See this
Jerrum and Sinclair and
Lecture 3 in this set of notes by Bela Bollobas