MATH 249 – Algebraic combinatorics, Fall 2019

Class times: M, W, F 10:10-11:00, 740 Evans.

Office hours: M, F 11:00-12:00, 933 Evans.

Instructor: Sylvie Corteel

e-mail: lastname at berkeley dot edu

Course homepage:

Office: 859 Evans

Other combinatorial activities (please register) MATH 290 Research seminar CCN15370 MATH 290 Reading seminar CCN15355

Textbook: The art of counting by Bruce Sagan

Further reading: Enumerative Combinatorics 1 and 2, by Stanley. Algebraic combinatorics by Stanley. The symmetric group by Bruce Sagan. Young tableaux by Fulton. A course in enumeration by Aigner.

Prerequisites: Math 55, 110, 113, 172

Grading: Homework – 50%, Presentation – 25% each, Final paper – 25%

Homework Policies: Homework will typically be assigned every other week and collected the following at the beginning of the class. No homework will be accepted after class for any reason. You may work together on homework problems, but your solutions should be written up independently and answers must be given in understandable form.

Special accommodations: In case of disability, extracurricular activities, or religious holidays, please follow official university procedure.





08/28 and 08/30

Fibonacci numbers, permutations and trees

Chapter 1

09/04 and 09/06

Trees, partitions, lattice paths

Chapter 1

Homework 1 due 9/18

09/09, 09/11, 09/13, 09/16

Counting with signs: inclusion-exclusion, sign reversing involutions, Reflection principle, LGV lemma, Matrix tree theorem

Chapter 2

09/18, 09/20, 09/23, 09/25

Ordinary generating functions

Chapter 3

Homework 2 due October 14

09/27, 09/30, 10/02

Exponential generating functions. Lagrange inversion

Chapter 4 (Sagan) Chapter 5 (Enumerative Combinatorics 2 by Stanley)

10/04, 10/07, 10/09 (cancelled - power outage), 10/11 (cancelled - power outage)

Symmetric functions

Chapter 7

Homework 3 due October 28

10/14, 10/16, 10/18, 10/21, 10/23, 10/25

Symmetric functions (cont.), Vertex operators

Chapter 7 (Sections 7.2, 7.3 and 7.8) Chapter 5 of Guillaume Chapuy's notes

Sketch of HW2 solutions

10/28 (cancelled power outage), 10/30, 11/01, 11/04

Symmetric functions (cont.): P-partitions, RSK algorithm

Chapter 7 (Sections 7.4 and 7.6)

Homework 4 due 11/13

11/06, 11/08, 11/11 (no class, holiday)

Generalizations of Schur polynomials: skew Schur, Hall Littlewood

Stanley Chapter 5 Section 7.9, 7.10, Appendix 1.3 Stanley Chapter 5 Chapter 3

11/13, 11/15, 11/18, 11/20

Chromatic symmetric functions, Group actions, Cyclic Sieving phenomenon

Sagan: section 7.9, sections 6.1, 6.2, 6.6, appendix A, 7.10. Survey paper on cyclic sieving phenomenon

11/22 and 11/25

Quasisymmetric functions. Mobius inversion

Sagan: sections 8.1 and 8.2. sections 5.1, 5.4 and 5.5 Survey paper (extra reading)

Homework 5 due 12/04

12/02, 12/04

Quasisymmetric functions

Sagan: sections 8.3, 8.5 and 8.6.

12/06 and 12/09

Presentations (15min per person)
Dec 6th (Evans 740) 9:00 Aprilia 9:20 Tristan 9:40 Marvin 10:00 Yelena, Yulia and Rikhav
Dec 6th (Evans 939) 1:30 James 1:50 Robert 2:10 Eric
Dec 9th (Evans 748) 9:00 Max, Jonathan 9:40 Suhyeon 10:00 David 10:40 Yueqing, Harry 11:20 Andrew

Paper is due on 12/13

Projects need to chosen by October 18th. You can do the project by yourself or with another student. You will be required to write a text and make an oral presentation. The paper is due on December 13th. The presentations will be on December 6th and 9th.
Parking functions and trees
Survey on parking functions by Catherine Yan

Lattice paths
Survey on lattice path enumeration by Christian Krattenthaler

Lattice paths and coefficientwise Hankel total positivity
Slides by Alan Sokal
Lattice paths and branched continued fractions: An infinite sequence of generalizations of the Stieltjes--Rogers and Thron--Rogers polynomials, with coefficientwise Hankel-total positivity by Mathias Petreolle, Alan D. Sokal, Bao-Xuan Zhu
Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions by Mathias Petreolle, Alan D. Sokal
Walks in the quarter plane
Walks in the quarter plane by Bousquet-Melou and Mishna
Walks avoiding a quarter plane by Bousquet-Melou
Walks in the quarter plane (Galois theory of differential equations) by Dreyfus, Hardouin, Roques and Singer

Triangulations and frieze patterns
SL_2 tilings and triangulations by Bessenrodt, Holm and Jorgensen
Survey on Frieze patterns by Sophie Morier-Genoud
Snapshot on Frieze and tilings by Thorsten Holm

Cluster algebras: finite type classification
Paper by Fomin and Zelevinsky
Chapter by Fomin, Williams and Zelevinsky
A Cluster expansion formula by Ralf Schiffler

Quasisymmetric functions
Survey on quasisymmetric functions by Sarah Mason

Alternating sign matrices
How the alternating sign matrix conjecture was solved
Book by David M. Bressoud Math library
Diagonally and antidiagonally symmetric alternating sign matrices of odd order by Behrend, Fischer and Konvalinka Robbins Prize announcement

Lagrange inversion
Survey by Ira Gessel

Recent trends in algebraic combinatorics
Choose a chapter
The book edited by Barcelo, Karaali and Orellana

Handbook in Enumerative Combinatorics
Choose a chapter
The book edited by Bona

Combinatorics of Macdonald Polynomials
Survey paper