18.997: Probabilistic Methods in Combinatorics (Spring 2011)


Course description

Syllabus

Homework assignments:
Problem Set 1: Chapter 1, Exercises 1, 2, 4, 6, 8, 10. Due Thursday 2/24/11 in class.
Problem Set 2: Chapter 2, Exercises 1, 2, 5, 7, 9. Due Tuesday 3/8/11 in class.
Problem Set 3: Chapter 3, Exercises 1, 2, 3, 4, and Chapter 4, Exercises 1, 2, 3. Due Tuesday 3/29/11 in class.
Problem Set 4: Chapter 4, Exercises 4, 5, and Chapter 5, Exercises 3, 4. Due Thursday 4/7/11 in class.
Problem Set 5: Chapter 6, Exercises 1, 3, and Chapter 7, Exercises 2, 3. Due Thursday 4/21/11 in class.
Problem Set 6: Chapter 9, Exercises 1, 2, and the following two part problem. Due Thursday 5/12/11 in class.
The Ramsey number r(H) is the minimum N such that every 2-edge-coloring of K_n has a monochromatic copy of H.
Part 1 (7 points) Show that every bipartite graph H on n vertices with maximum degree O(log n) has Ramsey number r(H)=n^{O(1)}.
Part 2 (3 points) Show that every graph H on n vertices with average degree omega(log n) has Ramsey number r(H)=n^{omega(1)}.