Math 566: Combinatorial Theory

Syllabus

The syllabus can be found here.

Important Dates

  • Last day to add/drop without “W”: [2023-01-24 Tue]
  • Midterm: [2023-02-21 Tue] (in class)
  • Final Exam due: [2023-04-26 Wed] at 6pm

Office Hours

  • Tuesday’s 10:30am–11:30am (EH 3827)
  • Thursday’s 10:30am–11:30am (EH 3827)
  • Friday’s 2pm–3pm (EH 3827)

Textbook

The optional textbook is Algebraic Combinatorics by Richard P. Stanley, Springer, 2018. UM students can access the ebook here.

References

  • [AC] Algebraic Combinatorics by Richard P. Stanley, Springer, 2018. UM access.
  • [ArSt] Tilings by Federico Ardila and Richard P. Stanley, 2005. Link.
  • [Ma] Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra by Jiří Matoušek, 2010. Link.
  • [Wi] Generatingfunctionology by Herbert Wilf, Academic Press, 1990. UM access.

Homework Assignments

  1. Homework 1 due [2023-01-24 Tue]. Hints.
  2. Homework 2 due [2023-02-10 Fri]. Hints. Selected solutions (Canvas).
  3. Homework 3 due [2023-03-13 Mon]. Hints.
  4. Homework 4 due [2023-03-28 Tue].
  5. Homework 5 due [2023-04-18 Tue].

Notes

  1. Introduction to graph eigenvalues
  2. Properties of graph eigenvalues
  3. Walks in cubes and the Radon transform
  4. Random walks in graphs and hitting times
  5. Generating functions
  6. Stationary distributions of random walks in graphs
  7. Tilings
  8. Tilings of rectangular grid
  9. Posets
  10. Groups and group actions
  11. Group actions on Boolean algebras
  12. Partitions and q-binomial coefficients
  13. The Sperner porperty for L(m,n)
  14. Spanning trees and resistor networks
  15. Laplacian and the Matrix-Tree Theorem
  16. Spanning trees of regular graphs
  17. Directed Matrix-Tree Theorem and Eulerian tours
  18. Permutations, statistics, and pattern avoidance
  19. Standard Young tableaux
  20. Parking functions and tree inversions
  21. Gessel-Viennot method and plane partitions
  22. Some symmetric polynomials

List of Lectures

Date Topics Additional Reading Class Notes Additional Materials
[2023-01-05 Thu] Graph eigenvalues [AC, Ch 1] 1st half of 1 Handout
[2023-01-10 Tue] Graph eigenvalues and properties [AC, Ch 1] 2nd half of 1 + most of 2 Handout
[2023-01-12 Thu] Walks in a cube [AC, Ch 2] Rest of 2 + 1st page of 3 Handout
[2023-01-17 Tue] Walks in a cube, continued + random walks [AC, Ch 2] Rest of 3 Handout + Notes on matrix associated to a linear transformation
[2023-01-19 Thu] Random walks continued [AC, Ch 3] Most of 4 Handout
[2023-01-24 Tue] Random walks + generating functions + stationary distributions [AC, Ch 3 + Exercise 3.1] [Wi, Ch1] Rest of 4 + 5 + 6  
[2023-01-26 Thu] Tilings [ArSt 1--2], [Ma, Ch 22] First 3 pages of 7 Handout
[2023-01-31 Tue] Tilings continued   Rest of 7 Handout
[2023-02-02 Thu] Tilings of a rectangle + posets [AC, Ch 4] 8 + first 2 pages of 9 Handout
[2023-02-07 Tue] Posets and Sperner’s theorem [AC, Ch 4] pp 2--4 of 9  
[2023-02-09 Thu] Sperner’s theorem + group actions [AC, Ch 4+5] Rest of 9 + 10 Handout
[2023-02-14 Tue] Group actions on Boolean algebras [AC, Ch 5] First 2 pages on 11 Handout
[2023-02-16 Thu] Group actions on Boolean algebra continued [AC, Ch 5] Worksheet + Last page of 11 Worksheet
[2023-02-21 Tue] Midterm      
[2023-02-23 Thu] Partitions and q-binomial coefficients [AC, Ch 6] 12 Handout
[2023-02-28 Tue] Break      
[2023-03-02 Thu] Break      
[2023-03-07 Tue] Sperner property of L(m,n) + spanning trees [AC, Ch 6] 13 + First 2 pages of 14 Handout
[2023-03-09 Thu] Resistor networks   pp 2--5 of 14  
[2023-03-14 Tue] Resistor networks + incidence matrix [AC, Ch 9] pp 5--7 of 14, first 2 pages of 15 Handout
[2023-03-16 Thu] Laplacian + the Matrix-Tree theorem [AC, Ch 9] 15 up to proof of MTT Handout
[2023-03-21 Tue] Spanning trees of regular graphs, directed MTT, and Eulerian tours [AC, Ch 10] Rest of 15 + 16 + pp 1--2 of 17  
[2023-03-23 Thu] Proof of BEST Theorem + Applications [AC, Ch 10] pp 2--5 of 17 Worksheet
[2023-03-28 Tue] Permutations, statistics, and pattern avoidance   18 Handout
[2023-03-30 Thu] Chains in Young’s poset and standard Young tableaux [AC, Ch 8]   Worksheet
[2023-04-04 Tue] Standard Young tableaux [AC, Ch 8] 19  
[2023-04-06 Thu] Standard Young tableaux and RSK [AC, Ch 8] 19  
[2023-04-11 Tue] Parking functions and labeled tree inversions   20  
[2023-04-13 Thu] Gessel-Viennot method and plane partitions [AC, Ch 8] 21 Handout
[2023-04-18 Tue] Some symmetric polynomials   22  
Date published: Monday, January 2, 2023