Math 5707

Spring 2014

Graph Theory

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, 4^th edition 2010, corrected reprint 2012, ISBN 9783642142789; electronic version available from the author.

We plan to cover substantial portions from chapters 1 through 6 and selected topics from chapters 7 through 12. We may also supplement the text with outside material, and may consider some topics in non-enumerative combinatorics outside of graph theory.

Homework

There will be 5 problem sets assigned fortnightly, skipping the weeks with take-home exams.

Collaboration is encouraged, as long as you

1. understand your solutions,
2. write your solutions in your own words without copying, and
3. indicate the names of your collaborators.

If you copy work (or collaborate without indicating so), UMN academic dishonesty policies shall be applied.

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) Exam 1 (Solutions)
	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) Exam 2 (Solutions)
	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]) Exam 3 (Solutions)

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.

---