Math 530: Graph Theory (Combinatorial Mathematics I), Spring 2022
Professor: Darij Grinberg
Organization
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 chip-firing.
Level: graduate.
Course calendar
- All weeks:
- 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 format I can read (PDF, TeX or plain text if it works; no doc/docx!). If you submit 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 sandpiles and acyclic orientations.
Sources
- Comprehensive:
- J. A. Bondy, U.S.R. Murty, Graph theory, 3rd printing, Springer 2008. A standard text, often recommended. It covers most topics of this course.
- C. Berge, Graphs. One of my favorite books on the subject, containing all standard results as well as several less known ones.
- Oystein Ore, Theory of graphs, 4th printing, AMS 1974. Not as comprehensive as the previous two but still covering much of the standard material.
- Bela Bollobas, Modern Graph Theory, Springer 1998. Deep treatment of several topics, with hundreds of exercises.
- Reinhard Diestel, Graph Theory, 5th edition, Springer 2016. Goes very deep, but not an easy read due to the terseness.
- Gary Chartrand, Linda Lesniak, Ping Zhang, Graphs and Digraphs, 6th edition, CRC Press 2016.
- Dieter Jungnickel, Graphs, Networks and Algorithms, 4th edition, Springer 2013.
- Introductory:
- Oystein Ore, Graphs and their uses, AMS 1996. An updated version of a classical expository text from the 1960s. Rather shallow but supposedly really well-written.
- Edward A. Bender and S. Gill Williamson, Foundation of Combinatorics with Applications. Chapters 5--6 cover some graph-theoretical basics. See also Seminar in algorithmic combinatorics by Williamson.
- Bela Bollobas, Graph Theory: An Introductory Course, Springer 1971. An older edition of his Modern Graph Theory. "Introductory" in the Hungarian sense; covers a lot of material on its 180 pages.
- Christopher Griffin, Graph Theory: Penn State Math 485 Lecture Notes, version 2.0, 2021. Undergraduate notes with focus on applications and computation.
- David Galvin, Basic Discrete Mathematics (Spring 2021). A graduate course on combinatorics that includes some graph theory (specifically, counting trees and some extremal results). Check out both Course-notes.tex (notes) and main.tex (solved homework) on the Overleaf server.
- David Guichard, An Introduction to Combinatorics and Graph Theory, 2022. Chapter 5 offers a brief introduction to graphs.
- Frank Harary, Graph theory, Addison-Wesley 1969. One of the oldest texts on the subject. Doesn't prove much.
- Tero Harju, Lecture notes on Graph Theory, 24 April 2014.
- John Harris, Jeffry L. Hirst, Michael Mossinghoff, Combinatorics and Graph Theory, Springer 2008. Only the first chapter is really about graph theory in our sense. Errata.
- Robin J. Wilson, Introduction to Graph Theory, 5th edition, Pearson 2010.
- Mike Tait, Math 8790: Graph Theory, Spring 2021, 2021. Focus on extremal graph theory as well as algebraic and probablistic methods.
- Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, 6th June 2018. My favorite introduction to discrete mathematics: witty and full of interesting ideas. Despite its title, it is more than suited for maths majors. Chapters 10-13 cover some basic graph theory.
- Keijo Ruohonen, Graph theory, 2013. Algorithm-focused choice of topics (matroids and optimization strongly represented).
- Mitchel T. Keller, William T. Trotter, Applied Combinatorics, 2017. Undergraduate treatment of combinatorics targeted at computer science students; includes some theory of graphs and network flows.
- Laszlo Lovasz, Jozsef Pelikan, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyound, Springer 2003. Playful but not very rigorous account of various combinatorial topics, including some graph theory. Some corrections.
- Douglas B. West, Introduction to Graph Theory, 2nd edition, Pearson 2001. Somewhere between an introduction and a comprehensive text. Updates and corrections.
- Topics:
- Alexander E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp, David B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, 2008. An introduction to a new and beautiful subfield of graph theory: the study of sandpiles (= chip-firing) and rotors on digraphs. Highly recommended.
- Caroline J. Klivans, The Mathematics of Chip-firing, CRC 2019. A whole book on sandpiles.
- Nicholas A. Loehr, Combinatorics, 2nd edition, CRC 2018. This is mostly about enumerative combinatorics, not graph theory; however, the treatment of Pfaffians here is close to what I plan to do (if we have time for it this quarter). Incidentally, I prefer the first edition for its better treatment of generating functions, but the difference shouldn't matter much for Pfaffians.
- Stasys Jukna, Extremal Combinatorics, 2nd edition, Springer 2011. This includes extremal graph theory and Ramsey theory, but also a lot more. Errata.
- my talk The diamond lemma and its applications, as well as MathOverflow question #262508, as well as papers by Bezem/Coquand, Eriksson, and probably others I don't remember on the diamond lemma.
Back to Darij Grinberg's teaching page.