Math 566 Winter 2021
Combinatorial Theory

Lectures: Monday Wednesday Friday 11am-12pm, on Zoom. Link can be found on Canvas.

Instructor: Thomas Lam, tfylam@umich.edu

Office hours: held in Gather (link and times listed on Canvas site). Alternatively, we can talk after any Zoom class.

Course description: We will discuss applications of algebra to combinatorics and vice versa. Topics may include: graph eigenvalues, random walks, domino tilings, matrix tree theorem, electrical networks, Eulerian tours, permutations, partitions, Young diagrams, Young tableaux, Sperner's theorem, Gaussian coefficients, RSK correspondence, partially ordered sets, ...

Level: introductory graduate/advanced undergraduate

Prerequisites: formal proofs and linear algebra will be used throughout. Familiarity with basic notions in combinatorics is helpful.

Academic Integrity: Students are expected to have read and understood the LSA Community Standards of Academic Integrity. By taking this course, students are agreeing to abide by the wording and spirit of these standards.

Grading:
95% of grade is based on problem sets.
5% of grade is based on class participation (zoom lectures, email, ...).
There will be no exams.

Problem sets: There will be a problem set roughly every two weeks. Homework solutions must be typed in LaTeX and submitted to Gradescope.
At the front of your homework solution, please acknowledge any books, online sources, etc. consulted, and indicate other students you worked with on the homework.

References:
The course will have significant overlap with the following optional textbook:
[AC]  Algebraic Combinatorics: Walks, Trees, Tableaux, and More by R. P. Stanley, Springer, 2nd ed, 2018. Version of 2013 is available as pdf file

Additional reading:

[EC1]   [EC2]  Enumerative Combinatorics, Vol 1 and Vol 2, by R. P. Stanley, Cambridge University Press, 2011 and 2001. Volume 1 is available as pdf file

[vL-W]  A Course in Combinatorics by J. H. van Lint and R. M. Wilson, Cambridge University Press, 2001.

[Til] Tilings by F. Ardila and R. P. Stanley

Disabilities: If you think you need an accomodation for a disability, please let me know as soon as possible, and provide me with a Verified Individualized Services and Accomodations (VISA) form. The Services for Students with Disabilities (SSD) Office (G664 Haven Hall, webpage here) issues VISA forms.

List of lectures:

• January 20: Graph eigenvalues I ([AC, Chapter 1])
  
• January 22: Graph eigenvalues II
  
• January 25: Graph eigenvalues and walks
  
• January 27: Largest eigenvalue
  
• January 29: Cubes ([AC, Chapter 2])
  
• February 1: Random walks ([AC, Chapter 3])
  
• February 3: Stationary distributions
  
• February 5: Stationary distributions II
  
• February 8: Hitting times
  
• February 10: Domino tilings I (see [Til] for a survey on tilings)
  
• February 12: Domino tilings II
  
• February 15: Domino tilings of rectangles
  
• February 17: Partially ordered sets ([AC, Chapter 4])
  
• February 19: Sperner's Theorem I
  
• February 22: Sperner's Theorem II
  
• February 24: no class (well-being break)
  
• February 26: Group actions on boolean algebras ([AC, Chapter 5])
  
• March 1: Sperner's theorem for quotients of boolean algebras
  
• March 3: Examples of quotients
  
• March 5: Young diagrams ([AC, Chapter 6])
  
• March 8: Gaussian polynomials
  
• March 10: Pentagonal number theorem
  
• March 12: Young tableaux ([AC, Chapter 8])
  
• March 15: Sum of squares formula
  
• March 17: Robinson-Schensted-Knuth algorithm
  
• March 19: More RSK
  
• March 22: More RSK
  
• March 24: Hook length formula
  
• March 26: Plane partitions I
  
• March 29: Plane partitions II
  
• March 31: Longest increasing subsequences
  
• April 2: Schur functions
  
• April 5: Schur functions II
  
• April 7: Matrix Tree Theorem
  
• April 9: Matrix Tree Theorem II
  
• April 12: Cayley's formula
  
• April 14: Electrical networks I
  
• April 16: Electrical networks II
  
• April 19: Groves
  
• April 21: