Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


Chains of maximum length in the Tamari lattice

Authors: Susanna Fishel and Luke Nelson
Journal: Proc. Amer. Math. Soc. 142 (2014), 3343-3353
MSC (2010): Primary 05A15, 06A07; Secondary 05E05, 05A17
Published electronically: June 11, 2014
MathSciNet review: 3238412
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BB05] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266 (2006d:05001)
  • [BB09] 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 (2009m:05004),
  • [BFP11] 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 pp.. MR 2880681
  • [BK01] 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 pp. (electronic). MR 1877659 (2003c:05009)
  • [BP11] F. Bergeron and L. F. Préville-Ratelle,
    Higher trivariate diagonal harmonics via generalized Tamari posets,
    J. Comb. 3 (2012), no. 3, 317-341. MR 3029440
  • [BW97] 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 (98b:06008),
  • [DM47] A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305-313. MR 0021531 (9,75i)
  • [EG87] Paul Edelman and Curtis Greene, Balanced tableaux, Adv. in Math. 63 (1987), no. 1, 42-99. MR 871081 (88b:05012),
  • [FT67] 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 0238984 (39 #344)
  • [Ful03] 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 (2004c:05009),
  • [Hai92] Mark D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. 99 (1992), no. 1-3, 79-113. MR 1158783 (93h:05173),
  • [HLT11] Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas, Permutahedra and generalized associahedra, Adv. Math. 226 (2011), no. 1, 608-640. MR 2735770 (2012d:20085),
  • [HT72] 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 0306064 (46 #5191)
  • [Knu73] Donald E. Knuth, The art of computer programming. Volume 3, Sorting and searching. Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. MR 0445948 (56 #4281)
  • [Kra01] C. Krattenthaler, Permutations with restricted patterns and Dyck paths,: Special issue in honor of Dominique Foata's 65th birthday (Philadelphia, PA, 2000), Adv. in Appl. Math. 27 (2001), no. 2-3, 510-530. MR 1868978 (2002k:05005),
  • [Mar92] George Markowsky, Primes, irreducibles and extremal lattices, Order 9 (1992), no. 3, 265-290. MR 1211380 (94a:06015),
  • [Rea06] Nathan Reading, Cambrian lattices, Adv. Math. 205 (2006), no. 2, 313-353. MR 2258260 (2007g:05195),
  • [Sta84] 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 (86i:05011)
  • [Sta99] Richard P. Stanley,
    Enumerative combinatorics. Vol. 2,
    with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
    Cambridge Studies in Advanced Mathematics, 62,
    Cambridge University Press, Cambridge, 1999. MR 1676282
  • [Tam62] Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131-146. MR 0146227 (26 #3749)
  • [Thr52] R. M. Thrall, A combinatorial problem, Michigan Math. J. 1 (1952), 81-88. MR 0049844 (14,234g)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05A15, 06A07, 05E05, 05A17

Retrieve articles in all journals with MSC (2010): 05A15, 06A07, 05E05, 05A17

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

Keywords: Tamari lattice, maximal chains, shifted tableaux
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
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society