Instructor(s): Stoyan Dimitrov
Description: Bijections are one-to-one maps between two given sets of objects and finding a bijection implies that the two sets are equinumerous. Moreover, having such a map often reveals that seemingly unrelated objects are just different encodings of the same underlying structure (e.g., the objects in the "Catalan family": balanced parentheses, Dyck paths, binary trees, etc.). Such correspondences also allow transfer of known results from one well-studied model to another that is harder to analyze directly. For instance, uniform sampling from a given combinatorial class may be difficult, but a bijection to another class can make it straightforward.
Apart from being important, some bijections are also very beautiful, giving us real confidence that we understand a class of objects or a theorem (as oppose to the often non-insightful inductive or algebraic proofs). Yet, a bijective proof never comes for free, as one has to elucidate what the objects really are and to analyze some underlying algebraic or geometric structure.
The course aims to cover some of the most important bijective proofs and bijections between (finite) combinatorial objects. Examples include bijections related to partitions, compositions, permutations (and pattern-avoiding permutations), lattice paths, standard Young Tableau, alternating sign-matrices, etc. Eye-opening proofs and interpretations related to well-known objects and theorems (e.g., determinants, linear recurrences, the Pentagonal number theorem, the the hook-length formula) will be also considered.
Time and Place: TBD.Textbook: Excerpts from multiple sources will be used (see the list below).
Instructor: Stoyan Dimitrov (emailТoStoyan {at} gmail [dot] com).
Office Hours: TBD (write me an email beforehand) or by appointment.
Syllables:
| Week | Topic | Sources |
|---|---|---|
| 1 | Bijections related to combinatorial identities and Pascal’s triangle | §5 in Graham, Knuth, Patashkin [1] |
| 2 | Bijections related to Fibonacci numbers | Benjamin and Quinn [2] |
| 3 | Bijections related to the Catalan family | §2, part 1 in Viennot [3], Lai [4], Stanley [5] |
| 4 | Bijections related to lattice paths (Dyck, Motzkin, Schroder paths): the cycle lemma, the Chung-Feller theorem, the glove bijection, the butterfly bijection, polygon dissections, Laguerre histories, continued fractions. | §12.2 in Loehr [6], §4.2, part 1 in Viennot [3] |
| 5 | Midterm presentations | |
| 6 | Bijections related to partitions: Glashier's and Sylvester's bijections. Pentagonal number theorem: Franklin's proof. Jacobi's triple product identity. | Pak [7], §2 in Bressoud [8], Bressoud and Zeilberger [9] |
| 7 | Bijections related to trees. Two proofs of Cayley's formula (by Prufer and Joyal). | this paper + that paper on Joyal's proof |
| 8 | Bijections for permutations and pattern-avoiding permutations. Inversion sequences. Identities on derangements. Mahonian and Eulerian statistics (Foata’s bijection). | §4 in Kitaev [10] |
| 9 | Bijections related to Standard Young Tableaux (SYTs) | this presentation of P. McNamara based on this paper. Bijective proof of the hook-length formula. The RSK correspondence and related facts (jeu de taquin). |
| 10 | Bijections related to Alternating Sign Matrices (ASMs). Lindström-Gessel-Viennot lemma and Pfaffians. | Bressoud [8] |
Sources:
- Concrete Mathematics, R. Graham, D. Knuth, O. Patashkin
- Proofs that Really Count: The Art of Combinatorial Proof, A. Benjamin and J. Quinn
- The Art of Bijective Combinatorics, X. Viennot
- Bijections between Catalan objects, presentation by T. Lai
- Catalan numbers, book by R. Stanley
- Bijective Combinatorics, N. Loehr
- Partitions bijections, a survey, I. Pak
- Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture, D. Bressoud
- Bijecting Euler's Partitions-recurrence, D. Bressoud, D. Zeilberger
- Patterns in Permutations and Words, S. Kitaev
- The 250 bijective proof problems of R. Stanley and solutions (not well-written) to about 150 of them (by S. Dimitrov et al.).
- The classical book of Richard Stanley, "Enumerative Combinatorics", Vol. 1
- Handbook of Enumerative Combinatorics
- The list of bijective maps in FindStat.org: https://findstat.org/MapsDatabase/
Suggested topics for Final presentations (and recommended sources):
- Heaps of pieces, see part 2 in X. Viennot's online lecturesa>.
- The Theory of species by Joyal, see the book of Bergeron et al. + this presentation by I. Gessel and this one by F. Lastaria.
- The involution Principe of Garsia and Milne, see Ch. 2.3 of the book of B. Sagan.
- Lozenge and domino tilings, see Ch. 9 on Tilings (by J. Propp) in the Handbook of Enumerative Combinatorics.
- Bijections for Baxter families and related objects, see the article of S. Felsner et al.
- Cumulants and free probability, see the great lectures of J. Novak.
- Boltzman samplers for random generation, see Ch. IX of Analytic Combinatorics by Flajolet + the seminal article on the topic.
- Important reductions for NP-completeness, see the famous article of Karp.
- Rational and algebraic series in combinatorial enumeration, see the great article of Mireille Bousquet-Mélou.
- Bijections within the theory of binomial enumeration, see Ch.12 of "Topics in Combinatorial Mathematics" by C. L. Liu, 1972 (I can give you a copy).
- Bijective proof of the Vandermonde’s determinant formula, see the article of I. Gessel + Bressoud's article on a generalization of it.
- Lattice paths and the Rogers-Ramanujan identities, see Bressoud's paper.
- Bijections for Stirling permutations, see the article of S. Janson et al. (as a start).
- Bijections related to ASMs (picking this topic will give you both midterm and final presentation topics): pick two of the following papers -
article 1, article 2, article 3, article 4, article 5, article 6, article 7.
Suggested topics for Midterm presentations (over concrete articles):
- Bijective and Automated Approaches to Abel Sums, by Kalai and Zeilberger.
- Enumeration of permutations containing a prescribed number of occurrences of a pattern of length 3, by M. Fumek.
- Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude, J. Courtiel et al.
- A bijective proof of the hook formula for the number of column strict tableaux with bounded entries, by J. Remmel and R. Whitney.
- Combinatorics of rectangulations: Old and new bijections, by A. Asinowski et al.
- Cylindric growth diagrams, walks in simplices, and exclusion processes, by S. Elizalde.
- Hankel determinants and LGV, by M. Fumek
- On the Correspondence Between Integer Sequences and Vacillating Tableaux, Z. Berikkyzy et. al.
- A bijection between ordered trees and 2-Motzkin paths and its many consequences, E. Deutsch, L.Shapiro.
- An Equidistribution Involving Invisible Inversions, M. Coopman, M. Rubey.
- another article on a bijection (by your choice), e.g., some researchers with many bijective proof articles are David Callan, Emeric Deutsch, Louis Shapiro, Arthur Benjamin, Sergi Elizalde, Olivier Bernardi, Doron Zeilberger, various people in France (e.g. Éric Fusy, Guillaume Chapuy or the members of LaBRI).
[45%] Final presentations, 25 min each, Final's week
[35%] Midterm presentations, 15 min each, Week 5
[20%] Test during final's week - very easy, just to check whether you have roughly followed the lectures.
HALL OF FAME (Selected presentations): TBD