Combinatorics

Course Calendar

Updated 19 August 2016

This calendar is subject to revision throughout the term.

**Monday, 29 August:**Basic counting, binomial identities. Pages 15-19 in Applied Combinatorics by Keller and Trotter.-
**Wednesday, 31 August:**Binomial identities and partitions of m. Lattice paths and Dyck paths. Pages 19-25 in Applied Combinatorics by Keller and Trotter. -
**Friday, 2 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, 5 September:**Holiday-
**Wednesday, 7 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, 9 September:**Inclusion/Exclusion, continued. Counting derangements and the Euler phi-function. Pages 136-140 in Applied Combinatorics by Keller and Trotter.

**Monday, 12 September:**Generating functions: introduction. Pages 147-151 in Applied Combinatorics by Keller and Trotter.-
**Wednesday, 14 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, 16 September:**Nonlinear recurrence relations, counting RUBOTs, and exponential generating functions. Pages 186-188, 156-159 in Applied Combinatorics by Keller and Trotter.

**Monday, 19 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, 21 September:**Exponential families, continued. Slides 39-48 in Alan Frieze’s lecture notes. -
**Friday, 23 September:**Exam 1

**Monday, 26 September:**Probabilistic method: introduction. Hypergraph coloring. Pages 11-14 in The Probabilistic Method by Matousek and Vondrak.-
**Wednesday, 28 September:**More examples of the probabilistic method. Slides 9-22 in Alan Frieze’s lecture notes. -
**Friday, 30 September:**Intersecting sets and the Erdos-Ko-Rado Theorem. Pages 15-17 in The Probabilistic Method by Matousek and Vondrak.

**Monday, 3 October:**The Lovasz Local Lemma. Pages 297-301 in Applied Combinatorics by Keller and Trotter.-
**Wednesday, 5 October:**The Lovasz Local Lemma, continued. Pages 297-301 in Applied Combinatorics by Keller and Trotter. -
**Friday, 7 October:**Markov and Chebyshev inequalities. Pages 21-26 in The Probabilistic Method by Matousek and Vondrak.

**Monday, 10 October:**Sums of 0s and 1s; Chernoff bounds. Pages 41-42 in The Probabilistic Method by Matousek and Vondrak.-
**Wednesday, 12 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, 14 October:**Ramsey’s Theorem. Slides 5-7, 12-14 in Alan Frieze’s lecture notes

**Monday, 17 October:**Ramsey’s Theorem, continued. Slides 15-21 in Alan Frieze’s lecture notes-
**Wednesday, 19 October:**Exam 2 -
**Friday, 21 October:**Holiday

**Monday, 24 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, 26 October:**Turan’s Theorem, continued. Pages 1-2, 8 in Turan’s Graph Theorem by Aigner. -
**Friday, 28 October:**Erdos-Stone-Simonovitz Theorem, extremal numbers for bipartite graphs Notes: Section 1

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

**Monday, 7 November:**1-factors, Tutte's Theorem Notes, Section 3-
**Wednesday, 9 November:**Introduction to Posets, Pages 105-112 in Applied Combinatorics by Keller and Trotter -
**Friday, 11 November:**Exam 3

**Monday, 14 November:**Dilworth's Theorem: Pages 113-115 in Applied Combinatorics by Keller and Trotter-
**Wednesday, 16 November:**Dilworth's Theorem, continued. Pages 113-115 in Applied Combinatorics by Keller and Trotter -
**Friday, 18 November:**The subset lattice and interval orders. Pages 117-119 in Applied Combinatorics by Keller and Trotter.

**Monday, 21 November:**Interval orders. Pages 117-119 in Applied Combinatorics by Keller and Trotter.-
**Wednesday, 23 November:**Holiday -
**Friday, 25 November:**Holiday

**Monday, 28 November:**Identifying Interval orders. Pages 117-119 in Applied Combinatorics by Keller and Trotter, Additional notes-
**Wednesday, 30 November:**Properties of networks, Galton-Watson process and connectivity in G(n, p). Sections 21.2, 21.8 in Networks, Crowds, and Markets by Easley and Kleinberg -
**Friday, 2 December:**Galton-Watson, continued. Other epidemiology networks. Sections 21.3, 21.4 in Networks, Crowds, and Markets by Easley and Kleinberg

**Monday, 5 December:**Other edge-independent models: Chung-Lu model, Watts-Strogatz model, stochastic block model, Kleinberg small world network.-
**Wednesday, 7 December:**Some other graphs. Preferential attachment, RGG, GTG, SKG. -
**Friday, 9 December:**Exam 4