MIT OpenCourseWare

Browse materialsMIT 18.315 · Spring 2005

Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics

Subjects: Algebra · Geometry · Mathematics

Art: Anonymous painter,15th century, Westerner and Arab practicing geometry 15th century manuscript, 15th… · Public domain

Instructor: Prof. Igor Pak
Term: Spring 2005
Level: Graduate
What's inside: 1 lecture note · 1 reading · 47 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Course Introduction Ramsey Theorem Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.315 Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics, Spring 2005, Prof. Igor Pak — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

How this course was organized

What's here, and what isn't

A lecture sequence of 39 items is confirmed. Assignment and exam materials exist too, but MIT's own order for them could not be verified, so they're shown as materials below rather than a sequence.

Not included here

4 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely. (3 items)
Referenced in a table, but without MIT's own verified order, so it isn't used to claim a sequence.

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

38 files

Assignments

8 problem sets

Other materials from this course

vssver.sccSCC file Download

MIT OpenCourseWare, Prof. Igor Pak, 18.315 Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics, Spring 2005.

License: CC BY-NC-SA 4.0 · Edition: Spring 2005 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Other materials from this course

Lecture 1: Course Introduction Ramsey Theorem

Lecture 2: Additive Number Theory Theorems of Schur and Van der Waerden

Lecture 3: Lower Bound in Schur’s Theorem Erdös-Szekeres Theorem (Two Proofs) 2-Colorability of Multigraphs Intersection Conditions

Lecture 4: More on Colorings Greedy Algorithm Height Functions Argument for 3-Colorings of a Rectangle Erdös Theorem

Lecture 5: More on Colorings (cont.) Erdös-Lovász Theorem Brooks Theorem

Lecture 6: 5-Color Theorem Vizing’s Theorem

Lecture 7: Edge Coloring of Bipartite Graphs Heawood Formula

Lecture 8: Glauber Dynamics The Diameter Explicit Calculations Bounds on Chromatic Number via the Number of Edges, and via the Independence Number

Lecture 9: Chromatic Polynomial NBC Theorem

Lecture 10: Acyclic Orientations Stanley’s Theorem Two Definitions of the Tutte Polynomial

Lecture 11: More on Tutte Polynomial Special Values External and Internal Activities Tutte’s Theorem

Lecture 12: Tutte Polynomial for a Cycle Gessel’s Formula for Tutte Polynomial of a Complete Graph

Lecture 13: Crapo’s Bijection Medial Graph and Two Type of Cuts Introduction to Knot Theory Reidemeister Moves

Lecture 14: Kauffman Bracket and Jones Polynomial

Lecture 15: Linear Algebra Methods Oddtown Theorem Fisher’s Inequality 2-Distance Sets

Lecture 16: Non-uniform Ray-Chaudhuri-Wilson Theorem Frankl-Wilson Theorem

Lecture 17: Borsuk Conjecture Kahn-Kalai Theorem

Lecture 18: Packing with Bipartite Graphs Testing Matrix Multiplication

Lecture 19: Hamiltonicity, Basic Results Tutte’s Counter Example Length of the Longest Path in a Planar Graph

Lecture 20: Grinberg’s Formula Lovász and Babai Conjectures for Vertex-transitive Graphs Dirac’s Theorem

Lecture 21: Tutte’s Theorem Every Cubic Graph Contains Either no HC, or At Least Three Examples of Hamiltonian Cycles in Cayley Graphs of Sn

Lecture 22: Hamiltonian Cayley Graphs of General Groups

Lecture 23: Menger Theorem Gallai-Milgram Theorem

Lecture 24: Dilworth Theorem Hall’s Marriage Theorem Erdös-Szekeres Theorem

Lecture 25: Sperner Theorem Two Proofs of Mantel Theorem Graham-Kleitman Theorem

Lecture 26: Swell Colorings Ward-Szabo Theorem Affine Planes

Lecture 27: Turán’s Theorem Asymptotic Analogues

Lecture 28: Pattern Avoidance The case of S₃ and Catalan Numbers Stanley-Wilf Conjecture

Lecture 29: Permutation Patterns Arratia Theorem Furedi-Hajnal Conjecture

Lecture 30: Proof by Marcus and Tardos of the Stanley-Wilf Conjecture

Lecture 31: Non-intersecting Path Principle Gessel-Viennot Determinants Binet-Cauchy Identity

Lecture 32: Convex Polyomino Narayana Numbers MacMahon Formula

Lecture 33: Solid Partitions MacMahon’s Theorem Hook-content Formula

Lecture 34: Hook Length Formula

Lecture 35: Two Polytope Theorem

Lecture 36: Connection to RSK Special Cases

Lecture 37: Duality Number of Involutions in Sn

Lecture 38: Direct Bijective Proof of the Hook Length Formula

Lecture 39: Introduction to Tilings Thurston’s Theorem