Math 372

Combinatorics
Fall 2022

Current week   |   Moodle   |   Course information
Instructor: David Perkinson (schedule)
Texts: Office hours: 11–12 M, 3–4 TuTh, or by appointment or drop-in.
Week 1: August 28 - September 2
Monday: Walks in graphs. (lecture, tex file)

Some links that might help with eigenvectors and eigenvalues: Wiki page for eigenvalues and eigenvectors, Wiki page for diagonalization, see lectures 9, 10, and 11 in my 201 notes.


Wednesday: Walks on the complete graph. (lecture, tex file)
  • Reading: Chapter 1.

Friday: Random walks. (lecture, tex file)
  • Reading: Chapter 3.
Week 2: September 5 - 9
Monday: No class today (Labor Day).

Wednesday: Posets, chains, antichains, Sperner property. (lecture, tex, slides) (lecture, tex file)
  • Reading: Chapter 4 through the definition of the Sperner property.
  • Turn in: HW1 (Overleaf template)

Friday: Order matchings from order-raising operators. (lecture, tex file)
  • Reading: Chapter 4 through the proof of Lemma 4.5.
Week 3: September 12 - 16
Monday: \(B_n\) has the Sperner property. (lecture, tex file)
  • Reading: finish Chapter 4.

Wednesday: The symmetric group. Group actions. (lecture)
Friday: The quotient poset \(B_n/G\). (lecture)
  • Reading: Chapter 5 through Theorem 5.8.
Week 4: September 19 - 23
Monday: Review homework. Sperner property for \(B_n/H\). (lecture)
  • Reading: Chapter 5.

Wednesday: Sperner property for \(B_n/H\). Young diagrams. (lecture, tex file) (lecture)
Friday: Log-concave sequences and polynomials with real zeros. (lecture, tex file) (lecture, tex file)
  • Reading: Section of polynomials with real zeros at the end of Chapter 5.
Week 5: September 26 - 30
Monday: \(q\)-binomial coefficients and Young diagrams. Enumeration under symmetry. (lecture)
  • Reading: Chapter 6 and beginning of Chapter 7.

Wednesday: Enumeration under symmetry. Polya counting. (lecture)
Friday: Polya counting. (lecture)
  • Reading: Chapter 7.
Week 6: October 3 - 7
Monday: Proof of Polya's theorem. (lecture)
  • Reading: Chapter 7.

Wednesday: Generating functions: first example; the ring of formal power series. (lecture)
Friday: Calculus of ordinary generating functions. (lecture)
Week 7: October 10 - 14
Monday: Exponential generating functions. (lecture)

Wednesday: Applications. (lecture)
Friday: Dirichlet series. (lecture)
Week 8: October 24 - 28
Monday: Poset incidence algebra. (lecture)
  • Reading: lecture notes

Wednesday: Möbius inversion for posets (lecture, tex file)
Friday: Applications of Möbius inversion (lecture, tex file)
  • Reading: lecture notes.
Week 9: October 31 - November 4
Monday: Simplicial complexes. (lecture, tex file)
  • Reading: lecture notes.

Wednesday: Simplicial complexes. (lecture, tex file)
Friday: Order complexes. (lecture, tex file)
  • Reading: lecture notes.
Week 10: November 7 - 11
Monday: Cycles and cuts in graphs. (lecture)
  • Reading: Reading: Chapter 11 of our text and the lecture notes.

Wednesday: The discrete Laplacian. (lecture, tex file) (lecture, tex file)
Friday: Quick introduction to Smith normal form. (lecture, tex file) (lecture, tex file, slides).
  • Reading: lecture notes.
Week 11 November: 14 - 18
Monday: Structure theorem for finitely generated abelian groups. (lecture, tex file, slides).
  • Reading: lecture notes.

Wednesday: Matrix-tree theorem. (lecture, tex file, slides).
Friday: A tree bijection. (lecture, tex file)
  • Reading: lecture notes.
Week 12: November 21 - 25
Monday: Consequences of the matrix-tree theorem; tree bijections and kappa-inversions; rotor router example. Rotor routing and abelian sandpile reference. (Mathfest presentation, and see the lecture notes for last Friday.)
  • Reading: lecture notes from last week.

Wednesday: Firing posets I. (lecture, tex file, slides).
Friday: Thanksgiving break. No class today.

Week 13: November 28 - December 2
Monday: Distributive lattices. (lecture, tex file, slides).
  • Reading: lecture notes.

Wednesday: Firing posets II. (lecture, tex file, slides).
  • Reading: lecture notes.

Friday: Firing posets III. (lecture, tex file)
Week 14: December 5 - 10
Monday: Firing posets IV. (lecture)
  • Reading: Lecture notes.

Wednesday: TBA (lecture, tex file)
Friday: No class today.
The \(\LaTeX\) document preparation system