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:

Grading

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

Student Support Services (S3) and Student Disability Services

Schedule

The exact schedule of future topics is tentative.

T   R  
    9/ 6 Elementary counting
9/11 Binomial theorem 9/13 Partitions
9/18 Permutations 9/20 Permutations
9/25 Sieve 9/27 Generating functions
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
10/23 Trees 10/25 Trees
10/30 Connectivity 11/ 1 Connectivity
11/ 6 Eulerian and Hamiltonian cycles 11/ 8 In-class midterm #2
11/13 Matchings 11/15 Matchings
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
12/11 TBA    

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

Problem set Due date
PS 1 9/11
PS 2 9/18
PS 3 9/25
PS 4 10/2
PS 5 10/16
PS 6 10/23
PS 7 10/30
PS 8 11/13
PS 9 11/20
PS 10 11/27
PS 11 12/11

Midterm exams

Midterm 1 (10/11):