18.447

Course information:

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

Grading Information:

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.

Homework Assignments

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.)
Solutions are here

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. Solutions are here.

The midterm is here 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.

Lectures

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 Gilbert-Varshamov bound.

Tue. 09/21:

We covered two topics that I found on-line; section 2.1 of these notes and Section 2 of these notes.

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 number (7.3)

Tue. 10/19:

Start of Talagrand's inequality. Section 7.6 and 7.7

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: