Math 581: Topics in Graph Theory
Fall 2010
Matching Theory
Assignments
To the main course page.
You should do as many as you can of the exercises in the chapters we cover. Do a good job: it's better to do fewer well than more badly. I won't give specific assignments, except for a few problems to be handed in.
What is an exercise? Exercises are anything called an "exercise", and also anything else that is not proved (and is not a difficult result quoted from the literature).
Schedule
- 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.
Your written work should be a final draft and logically complete (all necessary steps written and explained).
- Fri. 9/3: 1.0.1, 1.0.3(b), 1.1.5.
- Fri. 9/24: 1.4.2, 1.4.3, 1.4.7.
- Fri. 10/15: X.1, X.4, 2.4.1 (detailed, complete proof), 2.4.3.
- Fri. 10/22: 3.1.4, 3.1.8, 3.1.10.
Mon. Wed. 11/3: X.6 [3.2.8, suff], X.7 [3.2.8, nec], X.8 [barrier], 3.3.2.- Fri. 11/12: 3.3.12, 3.4.15, 4.1.2, 4.1.5, 4.2.8, X.9 [G0].
- Fri. 11/19: 5.2.3, 5.2.4, X.10 [5.2.2c].
- Fri. 12/3: 5.3.5, X.12 [NASC], 5.5.15, 6.5.6, 7.1.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.