Syllabus

Course Meeting Times

Lectures: 3 sessions / week, 1 hour / session

Prerequisites

18.02 Multivariable Calculus and 18.06 Linear Algebra or 18.700 Linear Algebra

Description

This course analyzes combinatorial problems and methods for their solution. Prior experience with abstraction and proofs is helpful. Topics include:

• Enumeration
• Generating functions
• Recurrence relations
• Construction of Bijections
• Introduction to Graph Theory
• Network Algorithms
• Extremal Combinatorics

Textbooks

Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books]

We will cover Chapters 1 through 13. Additional lecture notes to be provided on the Matrix-Tree Theorem and Eulerian cycles.

Problem Sets

Problem sets are due at the end of lecture each Monday (or the first day of classes of that week if Monday is a holiday) for assignments of the previous week. Since solutions to problem sets will be made available shortly after the deadline for handing them in, in general late problem sets will not be accepted without a valid reason such as illness. A problem set that is one or two days late with a reason like "more time needed" might be accepted with a penalty, such as 15% off, if permission is granted before the problem set is due. (In this case the posting of solutions will be delayed.)

"Reasonable" collaboration is permitted on problem sets, but you should not just copy someone else's work or look up the solution from an outside source. On each problem set please write the names of those students with whom you have collaborated.

Exams

There will be two one-hour exams and a final exam. There is no curve, but I suspect the average grade will be B.

Grading

Grades will be determined by a weighted average of