Math 5707, Spring 2017, Darij Grinberg @ UMN

Math 5707, Spring 2017

Lecture notes (unfinished!). (Also, source code of the lecture notes, for those interested.)
Make sure to refresh your browser when you access these notes! Otherwise, you might be looking at an outdated (cached) version.

Please mail darijgrinberg=gmail#com (replace = by @ and # by .) for questions and comments.

UPDATE (2022): See Math 530: Graph Theory (Combinatorial Mathematics I), Spring 2022 for a new iteration of this course (not quite the same material, but a lot of overlap) with typed lecture notes.

Handwritten notes:

Since the LaTeXed notes seem to be coming into existence far slower than the class is going, I'll upload handwritten notes as well. These correspond more directly to what is on the blackboard, and lack some of the polish and completeness of the final lecture notes.

Lecture 5 (Hamiltonian paths and cycles).

Lecture 6 (digraphs, multigraphs, Eulerian paths and circuits, multidigraphs, criteria for Eulerian etc.): coming soon. [Part 1 of the notes.]

See Section 0.1 of homework set 2 solutions for various notations around multigraphs and digraphs (particularly, the meanings of walks, path and cycles).
Section 5.2 of David Guichard's An Introduction to Combinatorics and Graph Theory deals with Eulerian walks and Eulerian circuits (although it calls them Euler walks and Euler circuits, respectively).
Another proof of the Euler-Hierholzer theorem (every connected multigraph whose vertices all have even degrees must have an Eulerian circuit) can be found in Problem 10.7 of Lehman-Leighton-Meyer; note that he calls Eulerian circuits "Euler tours".
See also Jeremy Martin's slides for examples and a different algorithm for finding Eulerian walks and circuits.
A strongly connected digraph has an Eulerian circuit if and only if each vertex v satisfies deg⁺ v = deg^- v. This is proven similarly to the Euler-Hierholzer theorem.

Lecture 7 (Hamiltonian paths in digraphs and tournaments) (see also the sourcecode of these notes).

Lecture 8 (determinants, and proof of Vandermonde using tournaments) (see also the sourcecode of these notes, and an old handwritten version giving a slightly different variant of the proof).

Lecture 9 (trees and spanning trees).

Lecture 10a (centers of a tree; oriented spanning trees).

Lecture 10b (BEST theorem): See Chapter 10 of Richard Stanley's Algebraic Combinatorics, and my unofficial errata (note the corrected definition of an oriented tree). Notice that Stanley's notation differs from mine in some points (e.g., his "edges" are my "arcs", his "Eulerian tours" are my "Eulerian circuits", and his "outdeg" is my "deg⁺").

Lecture 11 (lower bound on independent set size, and 2-colorings).

Lecture 12 (matrix-tree theorem) by Travis Scrimshaw: compare

notes by Jacques Verstraete;
Chapter 10 of Richard Stanley's Algebraic Combinatorics (with my unofficial errata);
notes by Gregg Musiker on the undirected-graph case.

Lecture 13 (Cayley's formula; bipartite graphs; matchings; Hall's theorem):

Frankie Smith's final paper derives Cayley's formula similarly to how I did it (in its Section 3.1 -- but beware that he only states the matrix-tree theorem for undirected graphs!);
further proofs of Cayley's formula appear in the Appendix to Chapter 9 of Richard Stanley's Algebraic Combinatorics;
for much more about counting trees, see Moon's booklet (not needed for hw/exams);
for bipartite graphs, see Section 12.2 and 12.5 in Lehman-Leighton-Meyer.

Lecture 14 (König's theorem; systems of distinct representatives; Birkhoff-van-Neumann theorem):

König's theorem but with a different proof;
another source for König's theorem is Chapter 10 of Chris Thomson's MATH 239: Introduction to Combinatorics notes, which provides the same proof as Wikipedia (and derives Hall's theorem from König's -- i.e., the opposite direction from what we did in class);
scribe notes from a class by Lionel Levine provide the proof of König's theorem that we did in class, along with Hall's theorem on systems of distinct representatives;
see Section 8.1 of P. J. Cameron's Notes on Combinatorics for Hall's theorem on systems of distinct representatives (but beware: instead of deriving it from Hall's theorem on matchings, he simply proves it from scratch); Section 8.3 provides a neat application to Sudoku;
proof of Birkhoff-von Neumann theorem (not needed in hw/exams).

Lecture 15 (Menger's theorem and rederiving König and Hall from it; Tutte's theorem without proof; Ore-Ryser without proof):

Section 4.1 of Alexander Schrijver's A Course in Combinatorial Optimization is what I followed in class for stating and proving the directed versions of Menger's theorem;
König's theorem is easily derived from Menger's theorem (no good source yet, but it's really easy: just direct all edges of a bipartite graph (G; X, Y) from their X-vertex to the Y-vertex, and apply Menger's theorem to the sets X and Y);
I mentioned Tutte's theorem on non-bipartite matching without proof; see Michel Goemans's notes (chapter 1 and chapter 2) for a proper treatment with proofs;
for the Ore-Ryser theorem, the best source I have is a MathOverflow post by Fedor Petrov giving a laconic guide to the proof.

Note that in Lecture 15, only Menger's theorem is hw/exam material.

Lecture 16 (network flows) (see also the sourcecode of these notes, and an old, handwritten version):

Jeremy L. Martin's Lecture Notes on Algebraic Combinatorics, in its Section 11.1, handles all I'm doing in class rather neatly.
For further material and real-life applications (mostly to industrial planning), see Chapter 4 of Lex Schrijver's A Course in Combinatorial Optimization (just updated with corrected typos and improved exposition, as of 23 March 2017).
Timon Thalwitzer's diploma thesis Max-Flow Min-Cut appears to be a highly thorough and systematic treatment of various versions of max-flow/min-cut (I personally haven't read it).

Lecture 17 (more on network flows):

Hall's theorem and the generalization to m disjoint matchings.
Acyclicity and partitionability of flows.
Menger's theorem follows from max-flow/min-cut. And conversely (for integers).
Mentions of further results (faster algorithms, circulations, etc. -- a teaser of the rest of Chapter 4 of Lex Schrijver's A Course in Combinatorial Optimization).

Lecture 18 (Gallai-Milgram and stable matchings):

Gallai-Milgram theorem (Theorem 2.5.1 in Diestel, Graph Theory, 3rd edition 2005).
The König theorem (on matchings and vertex covers) and the Redei theorem (each nonempty tournament has a Hamiltonian path) follow from Gallai-Milgram.
Stable matchings (Section 6.4 in Lehman, Leighton, Meyer, Mathematics for Computer Science).

Lecture 19 (stable matchings continued, and Pfaffians):

How the "Mating Ritual" (the algorithm solving the Stable matching problem) fares if you allow polygamy (= college admissions problem = hospital residence problem), if you allow indifference (i.e., the rankings can have ties), and if you allow the "staying single" preference (i.e., remaining unmatched is preferred to some spouses).
Definition and basic properties of Pfaffians (unlike the Wikipedia, I am using crossing numbers instead of permutation signs); outline of the proof of det A = (Pf A)². Other than that, the closest a textbook comes to my notation is Section 12.12 of Nicholas Loehr, Bijective Combinatorics. See also Jeanette Nguyen, Perfect Matchings and Pfaffian Orientation and scribe notes from a class by Michel Goemans (warning: both have been written by undergraduates).

Lecture 20 (Pfaffians continued, hw4, a bit of sandpiles):

Pfaffians: the identity Pf (B^T A B) = det B • Pf A for any skew-symmetric n×n-matrix A and any n×n-matrix B.
Pfaffians: if A is an n×n-matrix, then the 2n×2n-matrix which (written as a 2×2-block matrix) has blocks 0, A (first row), -A^T, 0 (second row) has Pfaffian equal to det A.
Homework 4: solutions and common mistakes.
Sandpiles: just an introductory example. If you are curious, here is relevant literature:

Lecture 21 (sandpiles):

Sandpiles: basics on the sinkless case:
- Definitions (chip configuration, firing, Z-configuration, legal, stabilizing, finitary, infinitary).
- Any legal sequence for a configuration f is a subpermutation of any stabilizing sequence for f. ("Subpermutation" means "subsequence of a permutation".)
- A configuration is either finitary (i.e., has a legal stabilizing sequence, and all such sequences are permutations of each other; moreover, each legal sequence can be extended to a legal stabilizing sequence) or infinitary (i.e., it has no stabilizing sequences, but there are legal sequences of any length). See Lemma 2.2 (part 1) in Alexander E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp, David B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs.
- If the total number of chips is > |A|-|V|, then the configuration is infinitary.
- If the total number of chips is h, then f is infinitary if and only if there exists a legal sequence of length (h+1)^|V|.

Homework and other problems:

Homework set 0: a sample problem, with detailed solution to illustrate some ideas. The LaTeX sourcecode for use as a template for writing your own solutions.

Homework set 1 (due 1 Feb 2017, in class). Solutions by Jacob Ogden; solutions by Lauren Go; solutions by Nicholas Rancourt. Thanks to all three of you! A few comments.

Homework set 2 (due 15 Feb 2017, in class, please only submit 5 of the 7 problems). Solutions. Also, solutions by Nicholas Rancourt to problems 1ab, 2, 4, 5, 7.

Midterm 1 (due 27 Feb 2017, in class). Hints to the problems (draft, probably to be improved). Statistics.

Homework set 3 (due 8 Mar 2017, in class, please only submit 5 of the 8 problems). Solutions to Exercises 1, 2, 3, 4, 5, 7, 8. Also, solutions to Exercises 1, 2, 4, 5, 6(b) by Jacob Ogden (rather terse but really nice).

Homework set 4 (due 29 Mar 2017, in class, please only submit 5 of the 7 problems). Solutions to Exercises 3, 4, 5, 6 by Jacob Ogden. For exercise 7, see Corollary 10.9 in L. R. Ford (Jr.) and D. R. Fulkerson, Flows in Networks, 1962 (a preprint is freely available).

Midterm 2 (due 5 Apr 2017, in class). Solution sketches to all exercises. Also, Solutions to Exercises 1, 2, 3, 4, 5, 6, 7a by Nicholas Rancourt, and Solutions to Exercises 1, 2, 4, 5, 6, 7 by Sasha Pevzner. A few comments. Statistics.

Homework set 5 (due 26 Apr 2017, in class, please only submit 4 of the 7 problems). Solution sketches/hints (hastily written; my apologies for the errors to be expected). Solutions to Exercises 1, 3a, 6, 7 by Nicholas Rancourt.

Midterm 3 (due 3 May 2017, in class). Solutions by Nicholas Rancourt (note that 2 and 4 (b) can be done more easily). Solutions to Exercises 1, 2, 4, 5, 6 by Jacob Ogden. Statistics.

An exercise on source and sink mutations of acyclic quivers (LaTeX sourcecode).