Math 5707, Spring 2017

Darij Grinberg (203B Vincent Hall).

This site is moving to ! Please change your links and references.


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 for questions and comments.

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.]

Lecture 7 (Hamiltonian paths in tournaments).

Lecture 8 (determinants, and proof of Vandermonde using tournaments).

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

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

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

Lecture 15 (Menger's theorem and rederiving König and Hall from it; Tutte's theorem without proof; Ore-Ryser without 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):

Lecture 17 (more on network flows):

Lecture 18 (Gallai-Milgram and stable matchings):

Lecture 19 (stable matchings continued, and Pfaffians):

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

Lecture 21 (sandpiles):

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).

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.