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)|
|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
- No notes and electronic devices (including calculators, phones, etc.) may be used
Midterm 1 (10/11):
- Practice exam and solutions
- Material covered: Lectures 9/6–9/27. Problem Sets 1 to 4. Textbook (Bona) Chapters 3–8.1.2.
Midterm 2 (11/8):
- Practice exam and solutions
- You may bring one sheet of notes on letter-sized paper (front and back) in your own handwriting. Typed, printed, or photocopied notes are forbidden.
- Material covered: Lectures 10/2–10/30. Problem sets 5–7 and the first problem of Problem Set 8. Bona Chapter 8 and graph theory notes up to Section 3.4 (Theorem 3.5 Mader’s theorem was skipped).
- Topics covered:
- Ordinary and exponential generating functions, with emphasis on the composition and exponential formulas
- Basic notions of graph theory. Degrees, paths, cycles, etc.
- Trees: properties (equivalent characterizations) and counting (Cayley’s theorem)
- Connectivity: vertex- and edge-connectivity. Whitney’s theorem.