Math 192      Algebraic Combinatorics

Course description:
This is an introductory course in algebraic combinatorics. No prior knowledge of combinatorics is expected. While there are few prerequisites the course is meant to be challenging (but also a lot of fun). In particular, rigorous mathematical proofs are expected.

Prerequisites:
Familiarity with linear algebra and finite groups.

Textbook:
There is no textbook for this course. A large part of this course will follow R. Stanley's notes ``Topics in Algebraic Combinatorics'' from Math 192 in Fall 2000.

Problem sets: There will be problem sets roughly once a week. Collaboration on homework is permitted, but you are not allowed to just copy someone else's work. You have to mention on your problem set who you worked with and also which books or articles you used.

Problem Set 1

Problem Set 2

Problem Set 3

Problem Set 4

Problem Set 5

Problem Set 6

Exams: There will be one in-class exam. There will be no final exam.

Final Paper: There will be a final paper due at the end of reading period.

Grading: Problem sets (60%), Exam (10%), Paper (30%).

Possible Topics:
Algebraic graph theory:

• Graphs and the adjacency matrix.
• Walks on the cube.
• Trees and Cayley's formula.
• Graphs and the Laplacian matrix.
• Matrix Tree Theorem.
• Eulerian digraphs and oriented trees.
• Expanders?

• Symmetric group and statistics on permutations.
• Posets: Sperner's Theorem, Dilworth's Theorem.
• Group actions on boolean algebras.
• Polya Theory.

• Partition enumeration. Euler's Pentagonal Theorem.
• Young diagrams and $q$-binomial coefficients.
• Unimodality of Gaussian coefficients.
• Young tableaux and hook-length formula.

• Catalan numbers, trees and operads.
• Polytopes and convexity.
• Cycles, bonds, and electrical networks.
• Algebraic approaches to tiling problems.
• Introduction to combinatorial game theory.

Lectures:

• Lecture 1: Introduction. Adjacency matrix and eigenvalues of graphs.
• Lecture 2: Walks on the cube.
• Lecture 3: Walks on the cube continued. Sketch of generalization to Cayley graphs of abelian groups.
• Lecture 4: Expander graphs: definition, motivation. Spectral expansion implies combinatorial expansion.
• Lecture 5: Expander mixing lemma. Application to error amplification.
• Lecture 6: Random walks on expanders. Start permutation statistics.
• Lecture 7: Inversions versus major index. Catalan numbers and generating functions.
• Lecture 8: Two bijective proofs of the formula for Catalan numbers. 132-avoiding permutations.
• Lecture 9: Posets. Dilworth's Theorem. Hall's Theorem.
• Lecture 10: Sperner's Theorem.
• Lecture 11: Group actions on boolean algebras I.
• Lecture 12: Group actions on boolean algebras II.
• Lecture 13: Partitions and Young diagrams I.
• Lecture 14: Partitions and Young diagrams II.
• Lecture 15: Partition identities: Euler's Pentagonal, Jacobi Triple Product.
• Lecture 16: Burnside's Lemma. Polya Theory start.
• Lecture 17: Polya Theory.
• Lecture 18: Polya Theory examples.
• Lecture 19: Tableaux and hook-length formula. RSK algorithm.
• Lecture 20: Up-down operators on Young's lattice.
• Lecture 21: Schur functions. Cauchy Identity.
• Exam.
• Lecture 22: Operator approach to Schur functions. Trees, Cayley's formula.
• Lecture 23: Matrix Tree Theorem I.
• Lecture 24: Matrix Tree Theorem II.
• Lecture 25: Eulerian digraphs and tours.
• Lecture 26: Eulerian tours and Matrix Tree Theorem.
• Lecture 27: Electrical networks I.
• Lecture 28: Electrical networks II.
• Lecture 29: Conway's Tiling groups.
• Lecture 30: Thurston's tiling height function.
• Lecture 31: Barne's algebraic approach to tiling.
• Lecture 32: Survey of algebraic combinatorics.
• Lecture 33: Student presentations.
• Lecture 34: Student presentations.