Math 565: Combinatorics and Graph Theory

Professor: David E Speyer

Fall 2013

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, speyer@umich.edu

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.

Rough Syllabus

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

Enumerative graph theory

Optimization on graphs

Planar graph theory

Problem Sets

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

Calendar

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 are excellent
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 networks.
October 31: Expanders. Modeled on several sources, particularly notes of Tao and Fox.
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