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, 12 October:**Sums of 0s and 1s; Chernoff bounds. Pages 41-42 in The Probabilistic Method by Matousek and Vondrak.-
**Wednesday, 14 October:**Chernoff bounds and Azuma’s Inequality. Pages 41-42 in The Probabilistic Method by Matousek and Vondrak, and pages 13-16 in Concentration inequalities and martingale inequalities by Chung and Lu. -
**Friday, 16 October:**Ramsey’s Theorem. Slides 5-7, 12-14 in Alan Frieze’s lecture notes

**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, 26 October:**Extremal Problems: introduction. Turan’s Theorem. Pages 290-291 in Applied Combinatorics by Keller and Trotter. Pages 1-2, 8 in Turan’s Graph Theorem by Aigner.-
**Wednesday, 28 October:**Turan’s Theorem, continued. Pages 1-2, 8 in Turan’s Graph Theorem by Aigner. -
**Friday, 30 October:**Erdos-Stone-Simonovitz Theorem, extremal numbers for bipartite graphs Notes: Section 1

**Monday, 2 November:**E-S-S Theorem, continued; ex(n, C_4). Notes: Section 2-
**Wednesday, 4 November:**Matchings, Hall’s Theorem. Notes: Section 1, 2 -
**Friday, 6 November:**Stable Matchings, 1-factors. Notes: Section 2.1

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

**Monday, 30 November:**Max-Flow/Min-Cut, the Ford-Fulkerson Algorithm, continued. Pages 242-247 in Applied Combinatorics by Keller and Trotter.$-
**Wednesday, 2 December:**Combinatorial game theory: introduction. Impartial games, Nim. Pages 1-5, 9-11 in Game Theory Part I: Impartial Games by Ferguson. -
**Friday, 4 December:**Directed graphs and the Sprague-Grundy Theorem. Pages 14-18, 21-23 in Game Theory Part I: Impartial Games by Ferguson.

**Monday, 7 December:**Two-person zero sum games; strategies. Pages 4-7 in Game Theory Part II: Two-Person Zero-Sum Games by Ferguson.-
**Wednesday, 9 December:**Nash equilibria and the existence theorem. -
**Friday, 11 December:**Exam 4