Combinatorial theory: introduction to graph theory, extremal and enumerative combinatorics

Lectures: Three sessions / week, 1 hour / session

There are no official prerequisites for this course, though familiarity with combinatorics is assumed. Students should already be familiar with Catalan numbers, Ramsey Theorem, generating functions, Euler's theorem on Eulerian paths, 3-connectivity of convex polytopes in R^3, Chebychev's Inequality, Markov's Inequality, and finite groups.

There are four main textbooks used for this class:

Stanley, R. P. Enumerative Combinatorics. Vol. I and II. Cambridge, UK: Cambridge University Press, 1999. ISBN: 0521553091 (hardback: vol. I); 0521663512 (paperback: vol. I); 0521560691 (hardback: vol. II).

Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998. ISBN: 0387984917.

———. Extremal Graph Theory. New York, NY: Dover, 2004. ISBN: 0486435962.

Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000. ISBN: 3540663134.

There are eight problem sets, each weighted equally for your grade. Collaboration is encouraged with a few simple rules. On every problem not more than four people can collaborate. Every student writes her/his own solution. For each problem, all collaborators should be listed.

There are no exams in this course.

The entire grade is based on the eight problem sets.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare