Math 565: Combinatorics and Graph Theory
Professor: David E Speyer
Fall 2010
Course meets: Tuesdays and Thursdays 11:30-1:00, 316 Dennison
Text: A Course in Combinatorics, van Lint and Wilson, ISBN
978-0-521-00601-9
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-12 and Thursday 2:30-4:00. 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.html
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 each other, the
library, the internet and any other source for aid with your work
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.
On take-home exames, you may not consult with other people or
outside sources; you may consult your notes and textbook, and the
handouts I provide.
Rough
Syllabus
My philosophy for this course will be to give you a taste of a lot of
different areas of combinatorics. I'll focus on learning how to solve
specific problems and become comfortable manipulating formulae, rather
than learning big theorems. I've roughly divided my topics into three
sections: Generating functions, graph theory and matroids. I am open to suggestions for topics to
include. Note that I will try to avoid duplicating Prof. Lam's course "Combinatorial Theory II".
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, although I can't
promise success.
Generating functions
September 7: Introduction to basic enumeration, binomial
coefficients
Chapter 13
Problem Set 1, due September 14.
Solution Set 1
September 9: (Rosh Hoshanah, Prof. Lam substitutes for me) Rational
generating functions and linear recurrences
Notes
September 14: Partitions
Chapter 15
Problem Set 2, due September 21.
Solution Set 2.
September 16: Catalan numbers in their many guises
Parts of Chapter 14
September 21: Higher Catalan numbers, Planar Trees and Lagrange Inversion
Notes, see also handout from
Stanley, \emph{Enumerative Combinatorics}
Problem Set 3, due September 28
September 30.
Solution set 3
September 23: Higher Catalan numbers, Planar Trees and Lagrange
Inversion continued
Notes, see Chapter 14 for a different perspective
September 28: Exponential generating functions
Parts of Chapter 14
First Take Home Exam Distributed, due October 5
September 30: Catch-up, or selected applications
Graph theory
October 5: Graph theory terminology, connectivity and trees
Chapter 1
Problem Set 4
Solution Set 4
October 7: Eulerian Tours
October 12: Counting Eulerian Tours
Problem Set 5
Solution Set 5
Handout out from Enumerative Combinatorics
October 14: The matrix-tree theorem
Chapter 36
October 19: Fall break! Go jump in a leaf pile!
October 21: Walks, adjacency matrices and eigenvalues
Problem Set 6
Solution Set 6
October 26: The importance of the eigenvalue gap
Notes
Take home 2 distributed, due November 2
October 28: Applications of graph eigenvalues
Optimization on graphs
November 2: Matchings
Chapter 5
Problem Set 7
Solution Set 7
November 4: Flows
Chapter 7
November 9: Optimization over matchings and flows
Problem Set 8
Solution Set 8
November 11: The Stable Marriage Theorem
November 16: Spanning trees
Problem Set 9
Solution Set 9
November 18: Review or else the 5 color map theorem.
November 23: NP-completeness: What we can't do.
November 25: Thanksgiving break.
Matroids
November 30: Definition of matroids, matroid voacbulary
Handout: Chapter Two from Theory of Matroids, edited by Neil
White, authors Giorgio Nicoletti and Neil White
December 2: Matroids in graph theory
Take home 3 distributed, due December 9.
Handout: Chapter Six from Theory of Matroids, edited by Neil
White, author James Oxley
December 7: Optimization on matroids
December 9: The Tutte polynomial
Take home 3 due