Math 8669: Combinatorial Theory (Spring 2018)

Lectures: MWF 11:15-12:05 in Vincent Hall 213.

Instructor: Gregg Musiker (musiker "at" math.umn.edu)


Office Hours: (In Vincent Hall 251) TBA.

Course Description:

This is a continuation of Math 8668, taught by Prof. Pasha Pylyavskyy in Fall 2017. Topics include but are not necessarily limited to:
  • Exponential Generating Functions, Lagrange Inversion, and Species
  • Enumeration of Trees
  • Representation Theory of Finite Groups, especially the Symmetric Group
  • Symmetric Functions and their bases, partitions, and Young Tableaux
  • Coxeter Groups (time permitting)

  • The majority of the course will focus on Chapter 7 of Stanley's Enumerative Combinatorics Volume 2 (and related material), although we will also go through Chapter 5 of Volume 2.

    Prerequisites: Abstract algebra (groups, rings, modules, fields) as from 5285-5286 or 8201 and either Math 8668 or some combinatorics experience.

    Textbook:

    Enumerative Combinatorics Volume 2 by Richard Stanley.

    Recommended Texts:

  • Enumerative Combinatorics Volume 1. An online version is available here.
  • The Symmetric Group by Bruce Sagan
  • Linear Representations of Finite Groups by J. P. Serre (Chapters 1-3, 5)
  • Symmetric Functions and Hall Polynomials by Ian Macdonald
  • Young Tableaux by William Fulton
  • Generatingfunctionology by Herbert Wilf
  • Symmetric Functions, Schubert Polynomials and Degeneracy Loci (Chapter 1) by Laurent Manivel
  • Constructive Combinatorics by Dennis Stanton and Dennis White
  • Computer algebra systems (very helpful, but not essential):

    Sage, Maple, Mathematica, available in Math computer labs, and also (for CSE undergrads) for free downloads at CSE Labs. Some systems available on the Web, in particular the Sage Cell Server and Wolfram Alpha, are sufficient.

    Participation in class is encouraged. Please feel free to stop me and ask questions during lecture. Otherwise, I might stop and ask you questions instead.

    Grading:

  • Homework (100%): There will be 3 homework assignments, one due approximately every month. The first homework assignment is due on Monday February 12th.

    I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Homework should be brought to class, my office, or can be emailed to me, or left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained as credit might not be given for an unsupported answer or a solution that comes directly from Stanley's volume with no other comment. Complaints about the grading should be brought to me.

    All homeworks will be a running list of problems of which I will suggest you do at least a certain number, although there will be occasional required problems if the material is fundamental. I will often update the problem sets with additional exercises as the course proceeds. Remember to check back periodically.
  • Tentative Lecture Schedule (with related reading from Stanley EC2)

  • (W Jan 17) Lecture 1: Introduction to the Course and Review of Generating Functions (EC1, Sec 1.1)
  • (F Jan 19) Lecture 2: The Compositional Formula and Applications (5.1)
  • (M Jan 22) Lecture 3: The Exponential Formula (5.1), Review of Cycles (EC1, Sec 1.3), and the Cycle Index Poly (Sec 5.2)
  • (W Jan 24) Lecture 4: More on the Cycle Index Poly (Sec 5.2) and Derangements (EC1, Sec 2.2)
  • (F Jan 26) Lecture 5: Polya Theory (TAC, Chapter 7 and Sec 7.24)
  • (M Jan 29) Lecture 6: Polya Theory II (TAC, Chapter 7 and Sec 7.24)
  • (W Jan 31) Lecture 7: More applications of the Exponential Formula (5.2) and Tree Enumeration (Sec 5.3)
  • (F Feb 2) Lecture 8: Tree Enumeration II (Sec 5.3)
  • (M Feb 5) Lecture 9: Lagrange Inversion (Sec 5.4)
  • (W Feb 7) Lecture 10: Matrix Tree Theorem I (Sec 5.6 and TAC, Chapters 9-10)
  • (F Feb 9) Lecture 11: Matrix Tree Theorem II (Sec 5.6 and OCW MIT Lectures 26-27)
  • (M Feb 12) Lecture 12: Matrix Tree Theorem III (Sec 5.6 and OCW MIT Lectures 26-27)
  • (W Feb 14) Lecture 13: Introduction to Representation Theory (Secs 1.1-1.5 of Sagan or Secs 1.1-1.4 in Serre)
  • (F Feb 16) Lecture 14: Representation Theory II: Maschke's Theorem and Schur's Lemma (Secs 1.3, 1.5, 1.6 of Sagan or Secs 1.4, 2.2 in Serre)
  • (M Feb 19) Lecture 15: Representation Theory III: Characters and Orthogonality Relations (Secs 1.8-1.9 of Sagan or Secs 2.1, 2.3 in Serre)
  • (W Feb 21) Lecture 16: Representation Theory IV: Decompositions of Representations (Sec 1.10 of Sagan or Sec 2.4 in Serre)
  • (F Feb 23) Lecture 17: Representation Theory V: Tensor Products and More Decompositions (Secs 1.7, 1.11 of Sagan or Secs 1.5-1.6, 2.5-2.7 of Serre)
  • (M Feb 26) Lecture 18: Representation Theory VI: Restricted and Induced Representations (Sec 1.12 of Sagan or Chapter 3, Secs 7.1-7.3 in Serre)
  • (W Feb 28) Lecture 19: Representation Theory VII: Restricted and Induced Representations continued (Sec 1.12 of Sagan or Chapter 3, Secs 7.1-7.3 in Serre)
  • (F Mar 2) Lecture 20: Representation Theory VIII: Frobenius Reciprocity (Sec 1.12 of Sagan or Chapter 3, Secs 7.1-7.3 in Serre)
  • (M Mar 5) Lecture 21: Symmetric Functions I: Orders on Partitions and Elementary Symmetric Functions (EC2, Secs 7.1-7.4 or Secs 4.1, 4.3 of Sagan)
  • (W Mar 7) Lecture 22: Symmetric Functions II: Involution and Complete Homogeneous Symmetric Functions (EC2, Secs 7.4-7.6)
  • (F Mar 9) Lecture 23: Symmetric Functions III: Power Symmetric Functions and Scalar Products (EC2, Secs 7.7, 7.9)
  • (M Mar 12) Spring Break
  • (W Mar 14) Spring Break
  • (F Mar 16) Spring Break
  • (M Mar 19) Lecture 24: Symmetric Functions IV: Octahedron of Symmetric Functions, Cauchy Kernel, Scalar Products and Schur Functions (EC2, Secs 7.9-7.10)
  • (W Mar 21) Lecture 25: Symmetric Functions V: Schur Functions and Skew-Schur Functions (EC2, Secs 7.10-7.12 or Sec 3.3, 4.4 of Sagan)
  • (F Mar 23) Lecture 26: RSK and its consequences (EC2, 7.12 or Secs 3.1-3.3 of Sagan, Also Section 8 of Stanley's Topics in Algebraic Combinatorics)
  • (M Mar 26) Lecture 27: Representations of the Symmetric Group I: Classical Definition of Schur Functions, Young Subgroups and Tabloids (EC2, 7.15, Sagan 2.1)
  • (W Mar 28) Lecture 28: Representations of the Symmetric Group II: Specht Modules (Sagan, Secs 2.2-2.3)
  • (F Mar 30) Lecture 29: Jacobi-Trudi and the Murnaghan-Nakayama Rule (EC2, Sec 7.15, 7.17 or Sagan 4.6, 4.10))
  • (M Apr 2) Lecture 30: The Frobenius Characteristic Map (EC2, Sec 7.18 or Sagan 4.7)
  • (W Apr 4) Lecture 31: Representations of the Symmetric Group III: Submodule Theorem (Sagan, Sec 2.4)
  • (F Apr 6) Lecture 32: Representations of the Symmetric Group IV: Linear Independence of e_T's for T standard (Sagan, Secs 2.4-2.5)
  • (M Apr 9) Lecture 33: Representations of the Symmetric Group V: Garnir relations and e_T's span for T standard (Sagan, Secs 2.5-2.7)
  • (W Apr 11) Lecture 34: The Branching Rule and Young's Rule (EC2, 7.16 and Sagan, Secs 2.8-2.11)
  • (F Apr 13) Lecture 35: Gessel-Viennot and Jacobi-Trudi Revisited (EC1 2.7, EC2, 7.15-7.16 or Sagan 4.5)
  • (M Apr 16) Lecture 36: Plane Partitions and RSK (EC2 7.20-7.21)
  • (W Apr 18) Lecture 37: The Hook Length Formula (EC2 7.21 and Sagan 3.1)
  • (F Apr 20) Lecture 38: The Hook Length Formula II and Plane Partitions in a Box (EC2 7.21)
  • (M Apr 23) Lecture 39: Reverse Plane Partitions and Hillman-Grassl (EC2, 7.22, Sagan 4.2)
  • (W Apr 25) Lecture 40: Hillman-Grasl II (EC2, 7.22, Sagan 4.2)
  • (F Apr 27) Lecture 41:Symmetry of Schensted's Algorithm and its History (EC2, 7.12-7.13 and Chapter 7 Notes)
  • (M Apr 30) Lecture 42: Knuth Moves and Knuth Equivalence and k-increasing subsequences (Sagan 3.6-3.8)
  • (W May 2) Lecture 43: Jeu de Taquin and towards the proof of the Littlewood-Richardson Rule (EC2 Appendix A1.2-3, Sagan 3.9, 4.9)
  • (F May 4) Lecture 44: Glimpse of Coxeter Groups


  • Homework assignments (tentative)
    Assignment Due date Problems from Stanley EC2,
    unless otherwise specified
    Homework 1 Monday Feb 12 Do at least six of the following fourteen suggested problems:
            EC1 Chapter 1: # 7, 21, 40, 41ab;
            EC2 Chapter 5: # 1ab, 3ab, 5, 7ab, 9ab, 10abcd, 15abcd, 39, 41abc;
            Problem 1 - Names in Boxes
    Homework 2 Wednesday March 7 Problem Set 2 (Do at least seven of the thirteen suggested problems.)
    Homework 3 Monday April 30th Problem Set 3 (Do at least six of the nine suggested problems.)