18.211 Combinatorial Analysis
Fall 2018, MIT
Class meetings: Tuesdays and Thursdays 1–2:30pm in 2-135
Lecturer: Yufei Zhao (see website for contact info). Office hours: M 2:45-3:45pm & TR 2:30-3pm in 2-271
Please include “18.211” in the subject line of your emails
Undergraduate introduction to combinatorics. Roughly the first half of the semester will focus on enumeration, and the second half on graph theory.
Prerequisites: Calculus II (GIR) and linear algebra (18.06 or 18.700 or 18.701). Prior experience with abstraction and proofs is helpful
- Part I: Enumeration
- Bóna, A Walk Through Combinatorics, 3rd or 4th edition
- Part II: Graph Theory
- Graph theory notes by Sudakov
- Additional textbook references:
- West, Introduction to Graph Theory
- Diestel, Graph Theory
- Bondy and Murty, Graph Theory
3 in-class midterms worth 25% each, and homework for the remaining 25%
The exact schedule of future topics is tentative.
|9/ 6||Elementary counting|
|10/ 2||Generating functions||10/ 4||Generating functions|
|10/ 9||No class (Columbus Day)||10/11||In-class midterm #1|
|10/16||Generating functions||10/18||Introduction to graph theory|
|11/ 6||Eulerian and Hamiltonian cycles||11/ 8||In-class midterm #2|
|11/20||Planarity||11/22||No class (Thanksgiving)|
|11/27||Graph coloring||11/29||Graph coloring|
|12/ 4||Ramsey theory||12/ 6||In-class midterm #3|
All homework submissions are due at the beginning of the Tuesday lecture. Submissions may be either typed or legibly written. All steps should be justified.
Sources. At the top of each assignment, you must write either “Sources consulted: none” or a list of all sources consulted other than the course notes. Examples include: names of people you discussed homework with, books, other notes (including the ones listed in the references below), Wikipedia and other websites.
You should not look up solutions to homework problems online (or offline).
Collaboration policy. Reasonable collaboration is permitted. Everyone must write their solutions individually and acknowledge their collaborators.
Late policy. Late problem sets will not be accepted without a valid excuse such as illness
|Problem set||Due date|
- 80 min in-class midterms
- Closed-book. No notes and electronic devices (including calculators, phones, etc.) may be used
Midterm 1 (10/11):