Home Syllabus Calendar Homework
Math 21-301 Fall 2016
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, 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, 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