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

Teaching assistants: Pro Pakawut Jiradilok and Morris Jie Jun Ang

Please include “18.211” in the subject line of your emails

Course description

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

Textbooks/references:

• 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

Grading

3 in-class midterms worth 25% each, and homework for the remaining 25%

Student Support Services (S³) and Student Disability Services

Schedule

The exact schedule of future topics is tentative.

Homework

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

Gradebook

Midterm exams

• 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
• Closed-book.
• 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.

Midterm 3 (11/6):

• Practice exam and solutions
• You may bring two sheets of notes on letter-sized paper (total four sides front and back) in your own handwriting. Typed, printed, or photocopied notes are forbidden.
• Material covered:
  • Lectures 10/30 onward
  • Problem Sets 8–10
  • Graph theory notes sections 3–7 (the following proofs are skipped: Theorems 3.5, 5.16, 7.22) and the introductory part of Section 11 (before Section 11.1)
• Topics covered:
  • Connectivity: basic notions, Menger’s theorem and consequences
  • Eulerian tours and Hamiltonian cycles: condition for having an Eulerian tour, Dirac’s theorem and its rotation-extension proof technique
  • Matchings: Hall’s theorem and consequences, Kőnig’s theorem, Tutte’s theorem (statement), Petersen’s theorem, Tutte-Berge formula
  • Planar graphs: Euler’s formula and consequences, Kuratowski’s and Wagner’s theorems (statement)
  • Coloring: greedy coloring and degeneracy, Brook’s theorem (statement), 5-color theorem, 4-color theorem (statement), art gallery theorem, relationship to orientations, Mycielski’s construction, Hadwiger’s conjecture (statement)