Home Syllabus Calendar Homework
Math 21-301 Fall 2015
Combinatorics
Course Calendar
Updated 2 September 2015
This calendar is subject to revision throughout the term.
- Monday, 31 August: Basic counting. Pages 15-19 in Applied Combinatorics by Keller and Trotter.
- Wednesday, 2 September: Binomial identities and partitions of m. Lattice paths and Dyck paths. Pages 19-25 in Applied Combinatorics by Keller and Trotter.
- Friday, 4 September: Counting lattice paths and Dyck paths continued; the Catalan numbers. Binomial and multinomial theorems. Counting spanning trees. Pages 25-28, 88-90 in Applied Combinatorics by Keller and Trotter.
- Monday, 7 September: Holiday
- Wednesday, 9 September: Cayley’s formula and Prufer codes. Pages 90-91 in Applied Combinatorics by Keller and Trotter. The Principle of Inclusion/Exclusion. Pages 131-136 in Applied Combinatorics by Keller and Trotter.
- Friday, 11 September: Inclusion/Exclusion, continued. Counting derangements and the Euler phi-function. Pages 136-140 in Applied Combinatorics by Keller and Trotter.
- Monday, 14 September: Generating functions: introduction. Pages 147-151 in Applied Combinatorics by Keller and Trotter.
- Wednesday, 16 September: Generating functions and linear recurrence relations. Pages 5-10 in Generatingfunctionology by Wilf, pages 184-185 in Applied Combinatorics by Keller and Trotter.
- Friday, 18 September: Nonlinear recurrence relations, counting RUBOTs, and exponential generating functions. Pages 186-188, 156-159 in Applied Combinatorics by Keller and Trotter.
- Monday, 21 September: Exponential generating functions, continued. Exponential Families. Pages 156-159 in Applied Combinatorics by Keller and Trotter; slides 39-48 in Alan Frieze’s lecture notes.
- Wednesday, 23 September: Exponential families, continued. Slides 39-48 in Alan Frieze’s lecture notes.
- Friday, 25 September: Exam 1
- Monday, 28 September: Probabilistic method: introduction. Hypergraph coloring. Pages 11-14 in The Probabilistic Method by Matousek and Vondrak.
- Wednesday, 30 September: More examples of the probabilistic method. Slides 9-22 in Alan Frieze’s lecture notes.
- Friday, 2 October: Intersecting sets and the Erdos-Ko-Rado Theorem. Pages 15-17 in The Probabilistic Method by Matousek and Vondrak.
- Monday, 5 October: The Lovasz Local Lemma. Pages 297-301 in Applied Combinatorics by Keller and Trotter.
- Wednesday, 7 October: The Lovasz Local Lemma, continued. Pages 297-301 in Applied Combinatorics by Keller and Trotter.
- Friday, 9 October: Markov and Chebyshev inequalities. Pages 21-26 in The Probabilistic Method by Matousek and Vondrak.
- Monday, 19 October: Ramsey’s Theorem, continued. Slides 15-21 in Alan Frieze’s lecture notes
- Wednesday, 21 October: Exam 2
- Friday, 23 October: Holiday
- Monday, 9 November: 1-factors, Tutte's Theorem Notes: Section 3.
- Wednesday, 11 November: Introduction to Posets, Pages 105-112 in Applied Combinatorics by Keller and Trotter
- Friday, 13 November: Exam 3
- Monday, 16 November: Dilworth's Theorem, Pages 113-115 in Applied Combinatorics by Keller and Trotter
- Wednesday, 18 November: The Subset lattice and interval orders, Pages 117-119 in Applied Combinatorics by Keller and Trotter
- Friday, 20 November: Flows and cuts: introduction. Pages 235-238 in Applied Combinatorics by Keller and Trotter
- Monday, 23 November: Max-Flow/Min-Cut, the Ford-Fulkerson Algorithm. Pages 242-247 in Applied Combinatorics by Keller and Trotter.
- Wednesday, 25 November: Holiday
- Friday, 27 November:Holiday