A L G E B R A I C    C O M B I N A T O R I C S,   S p r i n g   2 0 1 1

Lectures: Monday, Wednesday and Friday, 12pm-1pm, in Science Center 310.

Lecturer: Paul Bourgade, office hours Wednesday 2-3pm, you also can email me (bourgade@math.harvard.edu) to set up an appointment or just drop by (Science Center 341).

Course description: the first part of the course concerns methods in enumerative combinatorics, such as generating functions, partially ordered sets and enumeration under group actions. Statistics of permutation groups will be a recurrent application of these general methods. The second part will be more properly about algebraic combinatorics, considering the links between representation theory, symmetric functions and Young tableaux. Important applications will be about random matrices from compact groups and, once again, permutation groups, by considering the statistics of longest increasing subsequences.

Prerequisites: notions on finite groups and linear algebra, no prior knowledge about combinatorics is required.

Textbooks: references often followed in this course will be Enumerative Combinatorics, by Stanley, volumes 1 and 2, and Representation Theory: A First Course, by Fulton and Harris.

Grading: problem sets (50%), midterm (15%) and a final project (35%).

A tentative schedule for this course is:

• Jan. 24. Motivations: bijective methods, generating functions and algebraic combinatorics for permutations.
• Jan. 26. The 12-fold way, generating functions, Stirling and Bell numbers.
• Jan. 28. Rational generating functions, Catalan numbers.
• Jan. 31. Exponential generating functions, the compositional formula, the exponential formula.
• Feb. 2. Generating functions: Lagrange inversion, k-ary trees.
• Feb. 4. Generating functions: partitions.
• Feb. 7. Posets (partially ordered sets), inclusion-exclusion.
• Feb. 9. Posets: Dilworth's and Sperner's theorems.
• Feb. 11. Posets: Möbius inversion.
• Feb. 14. Binomial posets, generating functions and alternating permutations.
• Feb. 16. The Lindstrom-Gessel-Viennot lemma, rhombus tillings of a hexagon.
• Feb. 18. Kirchoff's matrix tree theorem, Cayley's formula.
• Feb. 23. Eulerian cycles and De Bruijn sequences.
• Feb. 25. Chromatic polynomials and hyperplane arrangements.
• Feb. 28. Tauberian theorems, Erdös-Kac and other number-theoretic examples.
• March 2. Tauberian theorems and permutations statistics.
• March 4. Permutations fluctuations and logarithmic combinatorial structures.
• March 7. Permutations: the Chinese restaurant process and central limit for the number of cycles.
• March 9. Enumeration under group action: Burnside's lemma.
• March 11. Enumeration under group action: Polya's theorem.
• March 21. Enumeration under group action: random matrices over finite fields.
• March 23. Midterm
• March 25. Representations: Schur's lemma, characters.
• March 28. Representations of finite groups.
• March 30. Irreducible representations of the symmetric group: the Specht modules.
• April 1. Irreducible representations of the symmetric group: the Specht modules are the irreducible modules.
• April 4. Symmetric functions, Schur polynomials.
• April 6. The Cauchy identity, the hook-length formula.
• April 8. Schur polynomials and Young tableaux.
• April 11. Schur-Weyl duality.
• April 13. Traces and caracteristic polynomials of random matrices.
• April 15. The RSK algorithm, the Plancherel measure.
• April 18. Jeu de taquin.
• April 20. Shape of Young diagrams for the Plancherel measure (I)
• April 22. Shape of Young diagrams for the Plancherel measure (II)
• April 25. Discrete determinantal point processes.
• April 27. Fluctuations for longest increasing subsequences.

• Problem set 1.
• Problem set 2.
• Problem set 3.
• Problem set 4.
• Problem set 5.