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: math.berkeley.edu/~corteel/MATH249.html

Office: 859 Evans

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

Textbook: 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.

 Date Topics Reading Homework 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 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