Algebraic Combinatorics (FA21)

Instructor: Nadia Lafrenière (Kemeny Hall 318, nadia.lafreniere@dartmouth.edu)
Class schedule: MWF 8:50 - 9:55 AM, x-hour will be used only under special circumstances (e.g. extended illness of the instructor). Classroom is Haldeman 028.
Website for the class: Canvas; https://canvas.dartmouth.edu/courses/48603
Office hours: Monday 1:30-3:30 PM
PDF version of this syllabus

Course Objectives
Algebraic combinatorics is defined as the interactions between algebra and  combinatorics. Techniques from algebra may solve combinatorial problem and conversely. The goal of this class is to introduce some notions of combinatorics and to use the techniques from it along with algebra. The first part of the course will be dedicated to review principles from enumerative combinatorics, such as basic statistics, counting principles and generating functions. Going forward, we will apply these to three main topics:

• Partial ordered sets (posets): lattices, Möbius function and incidence algebra.  Sperner’s lemma.
   
• Group acting on a set and Pólya theory.  
• Young tableaux. Robinson-Schensted bijection and applications to permutation patterns. Promotion and evacuation.
  

Attendance and Health Policy

You are expected to attend class in person unless you have made alternative arrangements due to illness, medical reasons, or the need to isolate due to COVID-19. For the health and safety of our class community, please: do not attend class when you are sick, nor when you have been instructed by Student Health Services to stay home. My lectures notes are available on the course website, and I will provide the support you need to catch up on class material and submit your work. If needed, one-on-one office hours over Zoom will be offered.

In accordance with current College policy, all members of the Dartmouth community are required to wear a suitable face covering when indoors, regardless of vaccination status. This includes our classroom and other course-related locations, such as office hours. If you need to take a quick drink during class, please dip your mask briefly for each sip. Eating is never permitted in the classroom. The only exception to the mask requirement is for students with an approved disability-related accommodation. If you do not have an accommodation and refuse to comply with masking or other safety protocols, I am obligated to assure that the Covid health and safety standards are followed, and you will be asked to leave the classroom.

Content's schedule (tentative)

This schedule is tentative, and will be updated throughout the term. The list of references for each part might change as well, but you will find most of the content taught in the references that are listed here.

Homework assignments are due on Wednesdays, except for the first week.

Date	Content	References
September 13	Introduction; What is combinatorics	[EC1], § 1.1
September 15	Combinatorial proofs, Catalan numbers	[EC1], § 1.1; [Sta15]
September 17	The Twelvefold way	[EC1], § 1.2, 1.9
September 20	Generating functions: ordinary and exponential	[genfunc], § 1.3, 2.1, 2.2, 2.3
September 22	Counting partitions	[AOC], § 1.6; [AZ10], § 31
September 24	Posets: basic concepts and examples, lattices	[EC1], § 3.1, 3.3
September 27	Properties of lattices	[AOC], § 5.3
September 29	Incidence algebra and Möbius function	[EC1], § 3.5, 3.6, 3.7, [AOC], § 5.4, 5.5
October 1	Möbius inversion	[EC1], § 3.8, [AOC], § 5.4, 5.5, 5.8
October 4	Hyperplane arrangements through posets	[EC1], § 3.11
October 6	Matroids and posets	[Sta07], § 3.4
October 8	Sperner's Lemma	[AC], § 4
October 11	Group acting on sets: intro, Burnside’s Lemma	[AC], § 7
October 13	Pólya theory	[AC], § 7
October 15	Necklaces	[AC], § 7
October 18	Young tableaux, bumping and sliding	[YoungTab], § 1
October 20	Robinson-Schensted bijection	[SymmGr], § 1.10, 3.1, 3.2, 3.6, 3.9, 3.10
October 22	Increasing sequences	[SymmGr], § 3.3, 3.5
October 25	Statistics and q-analogues	[AOC], § 3.2
October 27	The cyclic sieving phenomenon	[RSW14]
October 29	Homomesy: intro	[Propp,Roby,2015]
November 1	Promotion and rowmotion on posets	[Str17]
November 3	Promotion: tableaux and posets	[Str17], [RSW14], papers to be added
November 5	Student presentations
November 8	Student presentations
November 10	Student presentations
November 12	Student presentations
November 15	Student presentations
November 16	Written part of project due

 

Combinatorics Seminar

Dartmouth hosts a combinatorics seminar on most Tuesdays, at 10:15. You are encouraged to attend it, and I will advertise it in class before each talk. More details can be found on this webpage: https://math.dartmouth.edu/~comb/.

 

Evaluation

The homework assignments will be available at least five days before they are due, and will be due each Wednesday (except for the first homework, that will be due Friday, September 17). There might be one or two problems that you will not be able to solve on the first day the problem set is available, but these will be marked.

Evaluation	Date	Value
Problem sets	Weekly	60%
Student presentations	November 5-15	20%
Written part of the final project	Due November 16	20%

Finding the right answer is not equivalent to solve a problem, and therefore your solution will be evaluated as a whole. Please, keep in mind while writing the assignments that I will not be with you when I will read it, so it must be complete.

The student presentations can be about any research paper in algebraic combinatorics, or chosen in a list of topics that will be given to you mid-October. If you prefer, your project could consist in implementing an algorithm from algebraic combinatorics into a  programming language, writing a tutorial on how to use mathematical software to solve a combinatorial problem, or contributing to an open-source software. Students having further ideas should talk to me about the project they have.

The presentations and projects can be done in teams of two students, but the project should be bigger (longer talk and paper, or broader software project).

Extension policy

Every student is granted an automatic extension for one problem set; you however have to tell me before the submission deadline. This policy does not apply to the final project, nor to students talks, given that this would involve scheduling issues. I might grant extensions after the automatic one based on special circumstances, but students will need to ask for it.

 

Textbook

There is no required textbook for the class. Instead, all notes will be written on the blackboard or given to students in printed format, and the tentative schedule tells you
what reference I’m using on what day. A list of references that I am using to design the course material follows in this syllabus. The main references for the course are at the
Baker library’s reserve (these are [EC1, EC2, AC, YoungTab, SymmGr, AOC, genfunc]), and some of them are freely available online (at least partially).

 

References

[AC] R. P. Stanley. Algebraic combinatorics. Walks, trees, tableaux, and more, second edition. Undergraduate Texts in Mathematics. Springer, Cham, 2018. Freely available without exercices at http://www-math.mit.edu/~rstan/algcomb/algcomb.pdf.[AOC] B. E. Sagan. Combinatorics: The Art of Counting, volume 210 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2020.

[AZ10] M. Aigner and G. M. Ziegler. Proofs from THE BOOK (4th ed.). Springer, 2010.

[EC1] R. P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012. Freely available online at http://www-math.mit.edu/~rstan/ec/ec1.pdf.

[EC2] R. P. Stanley. Enumerative combinatorics. Volume 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[genfunc] H. S. Wilf. generatingfunctionology. Academic Press, Inc., Boston, MA, second edition, 1994. Freely available at https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf. Only the first edition is available at the library.

[RSW14] V. Reiner, D. Stanton, D. White. What is ... cyclic sieving?, Notices Amer. Math. Soc., 61(2):169-171, 2014. Freely available online at https://www-users.cse.umn.edu/~reiner/Papers/WhatIsCSP_Notices.pdf.

[SaganCSP] B. Sagan. The cyclic sieving phenomenon: a survey. "Surveys in Combinatorics 2011,"  London Mathematical Society Lecture Note Series, Vol. 392, Cambridge University Press, Cambridge, (2011), 183-234. Freely available online at https://users.math.msu.edu/users/bsagan/Papers/Old/csp-lms.pdf.

[Sage] The Sage Developers. SageMath, the Sage Mathematics Software System. http://www.sagemath.org.

[Sta07] R. P. Stanley. An introduction to hyperplane arrangements. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 389–496. Amer. Math. Soc., Providence, RI, 2007. Freely available online at http: //www-math.mit.edu/~rstan/arrangements/arr.html.

[Sta15] R. P. Stanley. Catalan numbers. Cambridge University Press, New York, 2015.

[Str17] J. Striker. Dynamical algebraic combinatorics: promotion, rowmotion, and resonance. Notices Amer. Math. Soc., 64(6):543–549, 2017. Freely available online at https://doi.org/10.1090/noti1539.

[SymmGr] B. E. Sagan. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001.

[YoungTab] W. Fulton. Young tableaux. With applications to representation theory and geometry, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997.

 

Students are encouraged to use software to solve the problems. For combinatorics, SageMath [Sage] is well-developed. It is furthermore free to use, to modify and to share. You can either download it for your personal computer running Windows, MacOS or Linux, or you can use it through CoCalc (https://cocalc.com/).

A list of further references for generic skills (note-taking, typing mathematics with LaTeX, using SageMath, ... ), is available on the website of the course.

 

Honor principle

Assignments and examinations serve both the purpose of fixing your ideas on a given subject and, for the evaluator, to assess the comprehension you have of the class and how the class material has been understood. None of these goals can be achieved if you hand out a solution that is taken from someone else or from a publicly available source. Nevertheless, students are allowed to work together on problems to explore their solutions. The homework you submit must reflect your own understanding, and you thus need to write your own copy of the solution, in your own words.

More information on the Academic Honor Principle can be found on Dartmouth’s website: https://students.dartmouth.edu/judicial-affairs/policy/academic-honor-principle

Student Accessibility and Accommodations

Students requesting disability-related accommodations and services for this course are encouraged to schedule a meeting with me as early in the term as possible. This conversation will help to establish how your accommodations will be implemented in my course and what role Student Accessibility Services (SAS) or its Testing Center may play in assisting. In order for accommodations to be authorized, students are required to register with SAS (Getting Started with SAS webpage; student.accessibility.services@dartmouth.edu; 603-646-9900) and to request an accommodation email be sent to me in advance of the need for an accommodation. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

 

Mental Health

The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. There are a number of resources
available to you on campus to support your wellness, including your undergraduate dean (http://www.dartmouth.edu/~upperde/), Counseling and Human Development
(http://www.dartmouth.edu/~chd/), and the Student Wellness Center (http://www.dartmouth.edu/~healthed/). Remember, mental and physical health should be your  number one priority!

 

Religious Observances
Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, preferably before the end of the second week of the term to discuss appropriate accommodations.

Financial Needs
All material for this class is aimed to be freely available, either at the library or online. If you encounter financial challenges related to this class (because of the workload for example), please let me know.