Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

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
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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9939-2014-12069-7
PII: S 0002-9939(2014)12069-7
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.