Course description

Syllabus

Homework assignments:

Problem Set 1: Chapter 1, Exercises 1,2,4,6,8,9,10. Due 2/24/14 in class.

Problem Set 2: Chapter 2, Exercises 1,3,7,8,9. Due 3/10/14 in class.

Problem Set 3: Chapter 3, Exercises 3, 4 and Chapter 4, Exercises 1,2,3,5. Due 4/14/14 in class.

Problem Set 4: Chapter 5, Exercises 1,3,4 and Chapter 6, Exercises 1,2,3.

Problem Set 5: Chapter 7, Exercises 1,2,3, and the following two part problem. Due Thursday 5/14/14 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)}.