Math 581: Topics in Graph Theory
Fall 2010

Matching Theory
Assignments

• Schedule of readings and exercises.
• Exercises to be handed in, with schedule.
• Additional homework exercises.
• Schedule of presentations.
• Errata and additions for the textbook. (This is important for your reading.)

To the main course page.

Schedule of Assignments

• Week 0 (8/30): Read most of the Preface to get an overview. (You'll understand the Preface better after studying a few chapters, but still, read it now.)
• Week .5 (8/30-31): Read "Basic Terminology" for basic graph theory and this book's terminology. We'll go over this in class, as necessary.
• Week 1 (8/31-9/3): Study Sections 1.0 - 1.1.
  Note that exercises include Lemma 1.0.1 and Corollary 1.1.7. I recommend 1.1.6 particularly.
• Week 1.5 (9/3-13): Study Section 1.2 and understand the algorithm by using it on an example.
• Week 2 (9/13-15): Section 1.3, including the elements of computational complexity (P and NP) and of matroid theory.
• Week 3 (9/20-24): Sections 1.3 - 1.4.
• Week 4 (9/27-10/1): Sections 2.0 - 2.3. Notice: No class on Fri. 10/1.
• Week 5 (10/4-8): Sections 2.3 - 2.5.
  (Truth: 2.5 is for enlightenment; just get the idea of these weird applications.)
• Week 6 (10/11-15): Sections 3.0 - 3.1.
• Week 7 (10/18-22): Sections 3.1 - 3.2.
• Week 8 (10/25-29): Sections 3.3 - 3.4, 4.0 - 4.2.
  • Recommended: Ex. 3.4.5, 4.1.3-4.
• Week 9 (11/1-5): Sections 4.2 - 4.3, 5.0 - 5.1.
• Week 10 (11/8-12): Sections 5.1 - 5.2.
• Week 11 (11/15-19): Sections 5.3 - 5.4.
  • Recommended: 5.2.9 (fun). Also, see if you can prove Lemmas 5.3.1-3 without reading the proofs in the book (to verify whether they are really routine, as I think they are).
• Week 12 (11/22-24): Sections 5.4 - 5.5, 6.5.
  • Recommended: Complete the proof of Corollaries 5.3.13 and 5.3.14.
  • Research: X.11 [ears].
• Week 13 (11/29-12/3): Sections 7.0 - 7.3.
  I suggest you study Box 7A but treat Box 7B as a reference to be read as needed.
  • Recommended: Ex. 5.5.4, 5.5.16-17, 5.5.27, 6.5.5, 7.1.10.
• Week 14 (12/6-10): Sections 7.3, 9.1.
  • Recommended: 7.3.7, ....
  • Research: X.11 [ears] again, now that we know more.

Hand-in Exercises

1. Fri. 9/3: 1.0.1, 1.0.3(b), 1.1.5.
2. Fri. 9/24: 1.4.2, 1.4.3, 1.4.7.
3. Fri. 10/15: X.1, X.4, 2.4.1 (detailed, complete proof), 2.4.3.
4. Fri. 10/22: 3.1.4, 3.1.8, 3.1.10.
5. Mon. Wed. 11/3: X.6 [3.2.8, suff], X.7 [3.2.8, nec], X.8 [barrier], 3.3.2.
6. Fri. 11/12: 3.3.12, 3.4.15, 4.1.2, 4.1.5, 4.2.8, X.9 [G0].
7. Fri. 11/19: 5.2.3, 5.2.4, X.10 [5.2.2c].
8. Fri. 12/3: 5.3.5, X.12 [NASC], 5.5.15, 6.5.6, 7.1.9.
9. Fri. 12/10: 7.3.2, 7.3.5.

"X" problems are on the page of additional exercises.

To the main course page.
To my home page.