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