Combinatorics (WI26)
- Combinatorial species and generating functions
- Symmetric functions and permutation enumeration
- Graph colouring and polynomials
- (Possibly) chip firing, cops and robbers
Evaluation:
We will have biweekly homework assignments. You are encouraged to collaborate but you must write your responses on your own and understand what you are submitting. I'm not too worried about homework deadlines but please submit everything you want to by the end of Tuesday March 17.
There will be presentations and a term paper near the end of the term. Please select a research paper to study and give a 20-30 minute talk on. Also, please write an expository paper of 4-10 pages summarizing the ideas and providing background context. I'll provide a list of potential papers to study, and you are encouraged to seek your own as well.
As this is a graduate course, evaluation for the graduate students will be much more informal. I won't give much feedback on the homework by default, but feel free to meet me in office hours to discuss it in further depth if you like.
Textbook:
There is no required textbook and everything you need to know will be in the lectures. Here are several useful references that you may enjoy for further reading:
- Enumerative Combinatorics by Richard Stanley
- Introduction to the Theory of Species of Structures by Bergeron, Labelle, and Leroux
- Proofs from THE BOOK by Aigner and Zeigler
- Counting with Symmetric Functions by Mendes and Remmel
Course schedule:
| Date | Topic | Homework |
| M Jan 5 | Cayley's formula for the number of trees | |
| W Jan 7 | Generating functions | |
| F Jan 9 | Generating functions and partitions |
|
| M Jan 12 | Combinatorial Species (Part 1) | |
| W Jan 14 |
Combinatorial Species (Part 2) |
|
| F Jan 16 | Operations on Species (Part 1) | Homework 1 |
| M Jan 19 | MLK Day - no class | |
| W Jan 21 | Operations on Species (Part 2) | |
| F Jan 23 | Research talk: Graphs missing a connected partition | |
| M Jan 26 | Symmetric functions (Part 1) | |
| W Jan 28 | Symmetric functions (Part 2) | |
| F Jan 30 | Counting with symmetric functions (Part 1) | Homework 2 |
| M Feb 2 | Open work session | |
| W Feb 4 | Counting with symmetric functions (Part 2) | |
| F Feb 6 | Counting with symmetric functions (Part 3) | Presentation topic proposal |
| M Feb 9 | Ribbon Schur functions | |
| W Feb 11 | Chromatic number of a graph | |
| F Feb 13 | Chromatic polynomials | Homework 3 |
| M Feb 16 | Chromatic symmetric functions (Part 1) | |
| W Feb 18 | Chromatic symmetric functions (Part 2) | |
| F Feb 20 | Chromatic quasisymmetric functions and unit interval graphs | |
| M Feb 23 | Hikita's formula | |
| W Feb 25 | The chromatic symmetric function of graphs glued at a vertex | |
| F Feb 27 | Alejandro:
A general grammar for the structural decomposition of graphs.
Abstract:
In work of Chapuy, Fusy, Kang, and Shoilekova, Tutte's structural decomposition of graphs is translated into a system of symbolic equations expressing any family of graphs (satisfying some stability conditions) in terms of its subfamily of 3-connected graphs. In this talk, I will explain their techniques and formalize some species-theoretical considerations that are briefly commented on in their article, as well as present an adaptation that includes graphs with loops.
|
Homework 4 |
| M Mar 2 |
Beth Anne: Combinatorial Matrix Inversion: A Local Proof Strategy Abstract:
Combinatorial transition matrices are ubiquitous in the world of symmetric functions. However, it can often be difficult to come up with bijections / sign-reversing involutions to prove that two such matrices are inverses. In a very recent paper, Khanna and Loehr show that when the objects counted by the entries of these matrices are built up in an incremental way, one can prove that these families of matrices are inverses by simply proving a "local" identity involving those incremental pieces. I'll present the main machinery that is developed in this paper and show how it can be applied to Kostka matrices and matrices involving brick tabloids.
|
|
| W Mar 4 | Alex: Newton polytopes of dual Schubert polynomials | |
| F Mar 6 |
David: Universal Structures & de Bruijn Graphs for Permutations: A Partial Survey Abstract: Mathematically elegant and useful in a variety of applications, universal structures like de Bruijn sequences have been of interest to humans for potentially thousands of years. Essentially, as one ``scrolls through" a universal structure, one encounters a safari through some class of smaller combinatorial objects. The original objects of study were long cyclic words that contained many smaller words as one looks at successive windows of contiguous elements; Chung, Diaconis, and Graham's 1992 paper expanded the question to other combinatorial objects. Of particular interest to us, we survey some results on universal structures and the de Bruijn graph for permutations. |
|
| M Mar 9 | Michaela |
Course Summary:
| Date | Details | Due |
|---|---|---|