Chains of maximum length in the Tamari lattice

Fishel, Susanna; Nelson, Luke

doi:10.1090/S0002-9939-2014-12069-7

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