**Lectures:** Monday and Wednesday 9:30-11, room 4-153

**Instructor:** Thomas Lam, room 2-169,
tfylam@mit.edu

**Office hours:** Monday and Wednesday, 1-2pm

**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: advanced undergraduate

**Grading:**
Based on several problem sets. There will be no exams.

**Going online:**
Beginning March 12,

- All problem sets are to be submitted via email.

- Next lecture is March 30.

- All office hours are cancelled.

- Students in the class should have received an invitation to join a class workspace (message board) on Slack.

**Recordings:**

- March 30 Young diagrams and Gaussian coefficients [AC, Chapter 6]
- April 1(Sorry for the technical problems in this lecture!) L(m,n) is Sperner [AC, Chapter 6]
- April 6 Euler's pentagonal number theorem
- April 8 Tableaux and Hook-length formula [AC, Chapter 8]
- April 13Proof of Hook-length formula
- April 15Frobenius formula and Robinson-Schensted Algorithm [AC, Chapter 8]
- April 22Growth diagram approach to RSK [EC2, Chapter 7]
- April 27Schur functions and plane partitions [AC, Chapter 8]
- April 29Matrix Tree theorem [AC, Chapter 9]
- May 4Matrix Tree theorem [AC, Chapter 9
- May 6Electrical networks
- May 11Groves and response matrices

**Problem sets:**
There will be problem sets every two weeks. Homework solutions must be typed in LaTeX and either submitted at the beginning of class, or emailed to me before midnight (i.e. by 11:59pm) of the due date.
Late homework grades are penalized 20% per late day.

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.

Problem Set 2 (Due Wednesday March 4) Solutions

Problem Set 3

Problem Set 4 (Due Wednesday April 15) Solutions

Problem Set 5 (Due Thursday April 30) Solutions

Problem Set 6 (Due Monday May 11)

**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.

**List of lectures:**

- February 3: Graph eigenvalues I ([AC, Chapter 1])

- February 5: Graph eigenvalues II

- February 10: Walks in cubes ([AC, Chapter 2])

- February 12: Random walks, stationary distribution ([AC, Chapter 3])

- February 18 (MIT Monday): Hitting times

- February 19: Counting domino tilings

- February 24: Domino tilings of rectangles

- February 26: Partially ordered sets

- March 2: Sperner's Theorem I

- March 4: Sperner's Theorem II

- March 9: Group actions on boolean algebras I

- March 11: Group actions on boolean algebras II

- March 16: No lecture (switching to online)

- March 18: No lecture (switching to online)

- March 23: No lecture (SPRING BREAK)

- March 25: No lecture (SPRING BREAK)