# 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

- Bóna,
- 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*

- West,

## Grading

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

Student Support Services (S^{3}) 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 | Coloring | 11/29 | 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

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 | |

## 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)