Math 5707
Spring 2014
Graph Theory
[ Course Calendar | Problem Sets ]
Basic Information
- Instructor: Jed Yang,
- Office hours: MW 13:00–14:30 (or by appointment) in Vincent 203B
- Lectures: MW 14:30–16:25 in Vincent 6
- Course website: http://math.umn.edu/~jedyang/5707.14s/
Course Information
This is a first course in graph theory, introducing a wide spectrum of classical topics such as matchings, graph colourings, planar drawings, flows, Ramsey theory, and the probabilistic method. Students are expected to know calculus, linear algebra, and have familiarity with proof techniques (e.g., mathematical induction). In particular, Math 5705 is neither required nor expected, as this course is designed to be a self-contained continuation in the sequence.
- Textbook: Graph theory, by Diestel, 4th edition 2010, corrected reprint 2012, ISBN 9783642142789; electronic version available from the author.
Homework
There will be 5 problem sets assigned fortnightly, skipping the weeks with take-home exams.Collaboration is encouraged, as long as you
- understand your solutions,
- write your solutions in your own words without copying, and
- indicate the names of your collaborators.
Late homework will not be accepted for credit; early homework is fine and can be left in my mailbox in the School of Mathematics mailroom near Vincent 105.
Problem sets will be posted on the course website and due at the beginning of lecture on the due dates. Refer to the calendar below for tentative due dates.
Examinations
There will be 2 midterm exams and a comprehensive final exam. All 3 are week-long, take-home exams. You may use resources such as books and the Internet. However, in contrast to homework, collaboration or consultation of human sources is not allowed on exams.Refer to the calendar below for tentative exam due dates.
Grading
Your grade will be determined by a weighted arithmetic mean of homework and exam scores.The higher score from the following two schemes will be automatically chosen for each student:
Scheme | Homework | Exam 1 | Exam 2 | Exam 3 |
---|---|---|---|---|
Scheme 1 | 25% | 20% | 20% | 35% |
Scheme 2 | 20%* | 20% | 20% | 40% |
* In Scheme 2, the worst homework will be dropped.
Calendar
To be updated throughout the term; tentative and subject to change.
Month | Monday | Wednesday | ||
---|---|---|---|---|
January | 22 | A brisk walk through graph theory | ||
27 | Class cancelled due to inclement weather | 29 | Basics, degree, paths (1.1–1.3) | |
February | 03 | Connectivity, Euler tours (1.4, 1.8) | 05 | Trees (1.5) |
10 | Hall's matching theorem (1.6, 2.1) | 12 | Stable matching theorem (2.1) [PDF notes]
Problem Set 1
| |
17 | Tutte's matching theorem (2.2) | 19 | Graph factors | |
24 | 2-connected graphs, contraction and minors (3.1, 1.7) | 26 | 3-connected graphs (3.2)
Problem Set 2
| |
March | 03 | Menger's theorem (3.3) | 05 | Linking vertices (3.5) |
10 | Plane graphs (4.1, 4.2) | 12 | Euler's formula (4.2) (20 proofs curated by David Eppstein) | |
17 | Spring Break | 19 | Spring Break | |
24 | Kuratowski's theorem (4.4) | 26 | Polyhedra
Problem Set 3
| |
April | 31 | Vertex colouring: Brooks's theorem (5.2) | 02 | Colouring planar graphs: list colouring (5.4), guarding art galleries, Fáry's theorem |
07 | Edge colouring: Vizing's theorem (5.3) | 09 | The probabilistic method
Problem Set 4
| |
14 | Random graphs (11.2) | 16 | Min-cut max-flow theorem (6.2) | |
21 | Baranyai's theorem [LW §38] | 23 | Hamiltonicity (undergrad research [Y]) | |
28 | Linear algebra [B §VIII.2] | 30 | Spectral graph theory [LW §31]
Problem Set 5
| |
May | 05 | Extended office hours | 07 | Extremal graph theory (7.1, [AZ §36]) |
Problem Sets
Problem sets will be posted here.Problem Set | Due Date | Problems | Remarks |
---|---|---|---|
Problem Set 1 | Wednesday, February 12 | 1 # 1, 3, 8, 14, 30. | Solutions posted on Moodle. |
Problem Set 2 | Wednesday, February 26 | 1 # 17, 23, 24; 2 # 1, 8, 12, 14, 18. | Hints. Solutions posted on Moodle. |
Problem Set 3 | Wednesday, March 26 | 1 # 29 (ignore the infinite case); 3 # 9, 16, 17, 18, 19, 25, 27. | Solutions posted on Moodle. |
Problem Set 4 | Wednesday, April 09 | 4 # 1, 6, 15, 19, 22, 23, 30. | Solutions posted on Moodle. |
Problem Set 5 | Wednesday, April 30 | 5 # 5, 6, 11, 12, 18, 19, 21, 26; 6 # 2, 3 (edge version only). | Solutions posted on Moodle. |
Supplemental Material
- Feb 12: The stable matching algorithm terminates
- Mar 24: Proper drawings of planar graphs
- Apr 02: A plane graph that is not 4-choosable, by Gutner (Theorem 1.7), proof on page 122.
- Apr 02: Colouring maps with four colours
References
- [AZ] Martin Aigner and Günter M. Ziegler , Proofs from THE BOOK, Springer; 4th ed., 2009.
- [B] Béla Bollobás, Modern Graph Theory, Springer, corrected, 2013.
- [LW] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2nd ed, 2001.
- [Y] Jed Yang, Vertex-pancyclicity of hypertournaments, Journal of Graph Theory 63 (2010), 338–348.
Announcements
- Feb 26: Exam 1 posted, due Mar 05.
- Mar 11: Exam 1 solutions posted; please check grades and comments on Moodle.
- Apr 09: Exam 2 posted, due Apr 16.
- Apr 22: Exam 2 solutions posted; please check grades and comments on Moodle.
- Apr 30: Exam 3 posted, due May 07.
- May 13: Exam 3 solutions and course grade lines posted; please check grades and comments on Moodle.
Last Modified 2014.05.13.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.