Combinatorics

Course Calendar

Updated 1 December 2016

This calendar is subject to revision throughout the term.

**Monday, 29 August:**Introduction: What is Discrete Mathematics? Counting subsets. Sections 1.1-1.3-
**Wednesday, 31 August:**Sequences, permutations, and ordered subsets. Sections 1.5-1.7 -
**Friday, 2 September:**Meet the binomial coefficients, an enumerativist's best friend. Section 1.8, 3.1, 3.5

**Monday, 5 September:**Holiday-
**Wednesday, 7 September:**Mathematical induction (remember that?) Section 2.1-2.2 -
**Friday, 9 September:**Inclusion/Exclusion. Section 2.3

**Monday, 12 September:**Inclusion/Exclusion, continued. Pigeonhole Principle. Sections 2.3-2.4-
**Wednesday, 14 September:**The binomial coefficients return, and get fancy: Multinomial Theorem and More Pascal's Triangle. Sections 3.1, 3.2-3.6 -
**Friday, 16 September:**More Pascal. Section 3.6-3.7. Introduction to recurrences: Fibonacci numbers. Section 4.1-4.2

**Monday, 19 September:**Fibonacci numbers, continued. Section 4.1-4.3-
**Wednesday, 21 September:**From recurrence to closed form: a formula for the Fibonacci numbers. Section 4.3, Solving non-homogeneous linear recurrences -
**Friday, 23 September:**Techniques for solving recurrences, continued. Intro to generating functions. Recurrences (eigenmethod) Generatingfunctionology by Wilf, Sections 1.1, 1.2

**Monday, 26 September:**Exam 1-
**Wednesday, 28 September:**Intro to generating functions, continued Generatingfunctionology by Wilf, Sections 1.1,1.2. -
**Friday, 30 September:**Counting with generating functions: products

**Monday, 3 October:**Counting with generating functions: products, continued.-
**Wednesday, 5 October:**Exponential generating functions Generatingfunctionology by Wilf, Section 2.3. -
**Friday, 7 October:**Exponential generating functions, continued.

**Monday, 10 October:**Exponential generating functions, continued.-
**Wednesday, 12 October:**Two-variable generating functions and exponential families. -
**Friday, 14 October:**Two-variable generating functions and exponential families, continued.

**Monday, 17 October:**Two-variable generating functions and exponential families, continued.-
**Wednesday, 19 October:**Graph theory basics. Sections 7.1, 7.2. -
**Friday, 21 October:**Holiday

**Monday, 24 October:**Exam 2-
**Wednesday, 26 October:**Traversibility. Section 7.3. -
**Friday, 28 October:**Trees and Cayley's Theorem. Sections 8.1-8.3.

**Monday, 31 October:**Trees meet traversibility: Traveling Salesman and related problems. Chapter 9.-
**Wednesday, 2 November:**Traveling Salesman and related problems, continued. -
**Friday, 4 November:**Bipartite graphs and matchings. Section 10.1, 10.2.

**Monday, 7 November:**Hall's Theorem. Section 10.3.-
**Wednesday, 9 November:**Finding perfect matchings with augmenting paths. Section 10.4. -
**Friday, 11 November:**Finding perfect matchings, continued.

**Monday, 14 November:**Combinatorial Geometry, introduction. Section 11.1.-
**Wednesday, 16 November:**Counting regions and convex polygons, Section 11.2-3. -
**Friday, 18 November:**Graph embeddings and planarity, introduction. Euler's Formula. Section 12.1.

**Monday, 21 November:**Exam 3-
**Wednesday, 23 November:**Holiday -
**Friday, 25 November:**Holiday

**Monday, 28 November:**Euler's formula and embedding graphs in other surfaces. Notes-
**Wednesday, 30 November:**Kuratowski's Theorem. Section 12.2 and supplementary notes -
**Friday, 2 December:**Kuratowski's Theorem, continued from supplementary notes.

**Monday, 5 December:**Coloring bipartite graphs. Section 13.1, 13.2.-
**Wednesday, 7 December:**Coloring. Section 13.3. -
**Friday, 9 December:**The Four-Color Theorem: coloring meets planarity. Section 13.4.