Chains of maximum length in the Tamari lattice
HTML articles powered by AMS MathViewer
- by Susanna Fishel and Luke Nelson PDF
- Proc. Amer. Math. Soc. 142 (2014), 3343-3353 Request permission
Abstract:
The Tamari lattice $\mathcal {T}_n$ was originally defined on bracketings of a set of $n+1$ objects, with a cover relation based on the associativity rule in one direction. Although in several related lattices the number of maximal chains is known, quoting Knuth, “The enumeration of such paths in Tamari lattices remains mysterious.”
The lengths of maximal chains vary over a great range. In this paper, we focus on the chains with maximum length in these lattices. We establish a bijection between the maximum length chains in the Tamari lattice and the set of standard shifted tableaux of staircase shape. We thus derive an explicit formula for the number of maximum length chains, using the Thrall formula for the number of shifted tableaux. We describe the relationship between chains of maximum length in the Tamari lattice and certain maximal chains in weak Bruhat order on the symmetric group, using standard Young tableaux. Additionally, recently Bergeron and Préville-Ratelle introduced a generalized Tamari lattice. Some of the results mentioned above carry over to their generalized Tamari lattice.
References
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
- Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, J. Combin. Theory Ser. A 116 (2009), no. 1, 55–75. MR 2469248, DOI 10.1016/j.jcta.2008.05.005
- Mireille Bousquet-Mélou, Éric Fusy, and Louis-François Préville-Ratelle, The number of intervals in the $m$-Tamari lattices, Electron. J. Combin. 18 (2011), no. 2, Paper 31, 26. MR 2880681, DOI 10.37236/2027
- Jason Bandlow and Kendra Killpatrick, An area-to-inv bijection between Dyck paths and 312-avoiding permutations, Electron. J. Combin. 8 (2001), no. 1, Research Paper 40, 16. MR 1877659
- François Bergeron and Louis-François Préville-Ratelle, Higher trivariate diagonal harmonics via generalized Tamari posets, J. Comb. 3 (2012), no. 3, 317–341. MR 3029440, DOI 10.4310/JOC.2012.v3.n3.a4
- Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945–3975. MR 1401765, DOI 10.1090/S0002-9947-97-01838-2
- A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305–313. MR 21531
- Paul Edelman and Curtis Greene, Balanced tableaux, Adv. in Math. 63 (1987), no. 1, 42–99. MR 871081, DOI 10.1016/0001-8708(87)90063-6
- Haya Friedman and Dov Tamari, Problèmes d’associativité: Une structure de treillis finis induite par une loi demi-associative, J. Combinatorial Theory 2 (1967), 215–242 (French). MR 238984
- Markus Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. in Appl. Math. 30 (2003), no. 4, 607–632. MR 1977846, DOI 10.1016/S0196-8858(02)00501-8
- Mark D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. 99 (1992), no. 1-3, 79–113. MR 1158783, DOI 10.1016/0012-365X(92)90368-P
- Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas, Permutahedra and generalized associahedra, Adv. Math. 226 (2011), no. 1, 608–640. MR 2735770, DOI 10.1016/j.aim.2010.07.005
- Samuel Huang and Dov Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combinatorial Theory Ser. A 13 (1972), 7–13. MR 306064, DOI 10.1016/0097-3165(72)90003-9
- Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
- C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 27 (2001), no. 2-3, 510–530. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000). MR 1868978, DOI 10.1006/aama.2001.0747
- George Markowsky, Primes, irreducibles and extremal lattices, Order 9 (1992), no. 3, 265–290. MR 1211380, DOI 10.1007/BF00383950
- Nathan Reading, Cambrian lattices, Adv. Math. 205 (2006), no. 2, 313–353. MR 2258260, DOI 10.1016/j.aim.2005.07.010
- Richard P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), no. 4, 359–372. MR 782057, DOI 10.1016/S0195-6698(84)80039-6
- Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
- Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131–146. MR 146227
- R. M. Thrall, A combinatorial problem, Michigan Math. J. 1 (1952), 81–88. MR 49844
Additional Information
- Susanna Fishel
- Affiliation: School of Mathematical and Statistical Sciences, Arizona State University, Tempe, Arizona 85287
- Luke Nelson
- Affiliation: School of Mathematical and Statistical Sciences, Arizona State University, Tempe, Arizona 85287
- Received by editor(s): March 26, 2012
- Received by editor(s) in revised form: October 17, 2012
- Published electronically: June 11, 2014
- Additional Notes: This work was partially supported by Simons Foundation Collaboration Grant No. 209806
- Communicated by: Jim Haglund
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 142 (2014), 3343-3353
- MSC (2010): Primary 05A15, 06A07; Secondary 05E05, 05A17
- DOI: https://doi.org/10.1090/S0002-9939-2014-12069-7
- MathSciNet review: 3238412