Math 565: Combinatorics and Graph Theory
Professor: David E Speyer
Course meets: Tuesdays and Thursdays, 11:30-1:00, 3088 East Hall
Text: Introduction to Graph Theory, Doug West, ISBN 9780130144003
I expect to jump around a lot in the text, and I will certainly not
cover all of the material in it. I hope you will find the text useful
as a source of alternate expositions for the material I cover. I will
write up or copy notes for subjects which I think are not dealt
with well in the book.
Office Hours: 2844 East Hall, Monday 10:00-12:00 and Tuesday
2:00-3:00. I will also be at tea in the math lounge (East Hall, second
floor) from 3-5ish on Mondays. Also, please feel free
to knock on my door or e-mail me at any time.
Professor: David E Speyer, 2844 East Hall, firstname.lastname@example.org
Course homepage: http://www.math.lsa.umich.edu/~speyer/565
Level: Mixed undergraduate-graduate.
Prerequisites: Calculus, Linear Algebra, and comfort with mathematics.
Student work expected: I will give problem sets every week, due
on Tuesdays, and take-home exams when we finish a topic.
Homework Policy: You are welcome to consult your class notes and textbook.
You are welcome to work together with your classmates provided (1) you list all people and sources who aided you, or whom you aided and (2) you write-up the solutions independently, in your own language. If you seek help from mathematicians/math students outside the course, you should be seeking general advice, not specific solutions, and must disclose this help. I am, of course, glad to provide help!
I do not intend for you to need to consult other sources, printed or online. If you do consult such, you should be looking for better/other expositions of the material, not solutions to specific problems.
You MAY NOT post homework problems to internet fora seeking solutions. Although I know of cases where such fora are valuable, and I participate in some, I feel that they have a major tendency to be too explicit in their help. You may post questions asking for clarifications and alternate perspectives on concepts and results we have covered.
Take home exams: On take-home exams, you may not consult with other people or outside sources; you may consult your notes and textbook, and the handouts I provide.
This course will discuss many aspects of graph theory: Enumerative
problems (counting substructures of graphs); optimization problems
(finding the best graph in some sense) and special techniques for
planar graphs (graphs you can draw in the plane).
I am a pure mathematician who tries to know
something about applied math, particularly applications to computer
science, so I'll try to bring out these connections as
appropriate. If you let me know what fields you are working in, I will
try to find applications in your subjects.
Here is a list of topics I hope to cover. We will have three midterm exams, one at
the end of each section; I will select dates for them later in the
Enumerative graph theory
- The matrix tree theorem
- Eulerian tours, de Bruijn sequences
- Counting flows, the Gessel-Viennot theorem
- Random walks on graphs
- Spectral methods in graph theory
Optimization on graphs
- Matchings, Hall's marriage theorem
- Optimal matchings
- The stable matching problem
- Optimization of flows, transportation problems
- Optimization of spanning trees
- Introduction to linear and integer programming
- Introduction to NP-completeness
Planar graph theory
- Euler's theorem
- The five color map theorem
- Planar duality
- Spanning trees in planar graphs, resistor networks
- Matchings in planar graphs
Problem Set 1, due September 10th in class. Solution Set 1
Problem Set 2, due September 17th in class. Solution Set 2
Problem Set 3, due September
24th 26th in class. Solution Set 3
Problem Set 4, due October 1st in class. Solution Set 4
MIDTERM 1 distributed October 1st in class, due October 8th in class.
Problem Set 5, due October 22nd in class. Solution Set 5
Problem Set 6, due October 29th in class. Solution Set 6
Problem Set 7, due November 5th in class. Solution Set 7
Problem Set 8, due November 19th in class (no problem set due November 12th). Solution Set 8. See Propp, Lattice Structures for Orientations of Graphs, Theorem 2, for
more on Problem 2.
Problem Set 9, due November 26th in class. Solution Set 9
September 3: Introduction to graph theory: skim Chapter 1
Enumerative graph theory
September 5: Trees: Chapter 2.1
September 10: The Matrix Tree Theorem: Chapter 2.2 "Enumeration of trees", "Spanning trees in graphs"
September 12: Example computations with the matrix tree theorem
September 17: Spanning trees and electrical networks. See David Wagner's Combinatorics of Electrical Networks for far more than I'll say.
September 19: Eulerian tours and de Bruijn sequences: Chapter 2.2
September 24: Counting Eulerian tours : Chapter 2.2
A taste of computational complexity
September 26: Introduction to computational complexity: P, NP and #P Scott Aaronson's lecture notes
October 1: NP completeness Aaronson's lecture notes are excellent again
October 3: #P completeness Largely based on Ben-Dor and Halevi, Zero-One Permanent is #P complete, an easier proof
Introduction to spectral methods
October 8: MIDTERM 1 due, Introduction to Graph Spectra
October 10: Spectra of highly regular graphs Background on the Hoffman-Singleton graph The original friendship theorem
paper, see Theorem 6
October 15: FALL BREAK!
In preparing the following lectures, I relied on a number of sources,
the most helpful of which were Jon Kelner's lecture notes.
October 17: Review of the spectral theorem
October 22: Random walks and diameter bounds. Similar to Kelner's fourth and sixth lecture
October 24: Cutting graphs. Similar to Kelner's third lecture but also drawing heavily on this presentation by Luca Trevisian
October 29: End of proof of Cheeger's inequality; examples of
graph drawing and partitioning. Today's Mathematica notebook is here, it uses the files in this folder. Note that this code is the quality
you'd expect for something I coded up in one night for a class demo:
In particular, the paths to the files are hard coded in and I left in
all the little computations we did in class today.
For those who want to explore, I started looking for data sets using
the answers to this Stackoverflow
question. In particular, I liked: some fun real
world examples, US road
networks, a lot of
pretty three dimensional objects, some large social
October 31: Expanders. Modeled on several sources, particularly
notes of Tao
November 5: Ramanujan graphs. Proof of the Alon-Boppana theorem
is similar to the proof given here, I
have not been able to figure out who originated this trick. Recent
breakthroughs on Ramaujan graphs here
November 7: No class, David in Chicago.
Some optimization problems
November 12: The Hall Marriage theorem. Chapter 3.1 and 3.2.
November 12: Optimal matchings concluded, begin optimal
flows. Chapter 4.3.
November 19: Max flow/min cut. Chapter 4.3
November 21: Linear programming, the simplex algorithm. My
presentation is pretty different from most books' presentations; a
google search for Simplex Algorithm will turn up many more standard
presentations. Wikipedia is as
good as any other online source that I found; my favorite print source
is Chapter 29 in Introduction to Algorithms
November 26: Linear programming duality. Again, my presentation
is idiosyncratic; see the above links.
November 28: Thanksgiving, no class.
Perfect matchings of planar graphs
These lectures are a tiny subset of Kenyon's notes.
December 3: Kasteleyn's method
December 5: Height functions
December 10: MIDTERM 2 due. Recent work on random perfect matchings