Math 530: Graph Theory (Combinatorial Mathematics I), Spring 2023
Professor: Darij Grinberg

Organization

Classes:
Tue, Thu 11:00 -- 12:20 in Curtis 353A (new location!).
Office hours:
Mon 11:00 -- 13:00 in Korman 263. Also by appointment on https://drexel.zoom.us/j/2350700617.
Notes:
As our text, we will use the notes from the 2022 version of this course.
Also, an (unedited) lecture diary of the present course is available (literally what I wrote in class, unpolished and undetailed, and missing any drawings).
Blackboard:
https://learn.dcollege.net/ultra/courses/_339106_1/cl/outline.
Gradescope:
https://www.gradescope.com/courses/523079.
Piazza:
http://piazza.com/drexel/spring2023/math530.
Instructor email:
darij.grinberg@drexel.edu

Course description

An introduction to the theory of graphs. We will discuss basic concepts and properties of finite graphs (both undirected and directed), covering in particular the theories of Eulerian trails, Hamiltonian paths, trees, tournaments and dominating sets. We will prove the max-flow-min-cut theorem of network theory and apply it to bipartite matching. If time allows, we will further see some more recent topics such as the diamond lemma.

Level: graduate.

Course calendar

Week 0:
Week 1:
Week 2:
Week 3:
Week 4:
Week 5:
Week 6:
Week 7:
Week 8:
Week 9:
Week 10:
No Copyright:
The above lecture notes and assignments have been released under the CC0 license, i.e., are dedicated to the public domain. They can be copied, modified and distributed without permission. See the license for details.

Grading and policies

Grading matrix:
  • 100%: homework sets. (The lowest score will be dropped if all homework sets are submitted.)
Grade scale:
These numbers are tentative and subject to change:
  • A+, A, A-: (80%, 100%].
  • B+, B, B-: (60%, 80%].
  • C+, C, C-: (40%, 60%].
  • D+, D, D-: (20%, 40%].
Homework policy:
  • Collaboration and reading is allowed, but you have to write solutions in your own words and acknowledge all sources that you used.
  • Asking outsiders (anyone apart from Math 530 students and me) for help with the problems is not allowed. (In particular, you cannot post homework as questions on math.stackexchange before the due date!)
  • Late homework will not be accepted.
  • Solutions have to be submitted electronically via Gradescope in a typewritten (NOT handwritten!) format. You can use LaTeX, your favorite office software, Google Docs or even plain text, but it must be typed (except for pictures, which you can draw by hand and scan/photograph). After several years of accepting handwritten solutions, I've come to the conclusion that they not only take much longer to grade, but are also more likely to be wrong or confusing, as the process of handwriting distracts from logically structuring your proofs and discourages editing. When submitting a PDF, make sure that it is readable and does not go over the margins. If there are problems with submission, send your work to me by email for good measure.
Expected outcomes:
The students should have an understanding of standard concepts of graph theory such as Eulerian tours, trees, matchings, tournaments and Hamiltonian paths. They should know classical combinatorial results such as Hall's marriage theorem, Turan's theorem and the Gallai-Milgram theorem, as well as the max-flow-min-cut theorem on network flows. They should have seen several proof techniques in graph theory and some newer developments such as the diamond lemma.

Sources

Comprehensive:
Introductory:
Topics:

Other resources

University policies:
Disability resources:

Back to Darij Grinberg's teaching page.