The enumeration of generalized Tamari intervals
HTML articles powered by AMS MathViewer
- by Louis-François Préville-Ratelle and Xavier Viennot PDF
- Trans. Amer. Math. Soc. 369 (2017), 5219-5239 Request permission
Abstract:
For any finite path $v$ on the square grid consisting of north and east unit steps, starting at (0,0), we construct a poset Tam$(v)$ that consists of all the paths weakly above $v$ with the same number of north and east steps as $v$. For particular choices of $v$, we recover the traditional Tamari lattice and the $m$-Tamari lattice.
Let $\overleftarrow {v}$ be the path obtained from $v$ by reading the unit steps of $v$ in reverse order, replacing the east steps by north steps and vice versa. We show that the poset Tam$(v)$ is isomorphic to the dual of the poset Tam$(\overleftarrow {v})$. We do so by showing bijectively that the poset Tam$(v)$ is isomorphic to the poset based on rotation of full binary trees with the fixed canopy $v$, from which the duality follows easily. This also shows that Tam$(v)$ is a lattice for any path $v$. We also obtain as a corollary of this bijection that the usual Tamari lattice, based on Dyck paths of height $n$, can be partitioned into the (smaller) lattices Tam$(v)$, where the $v$ are all the paths on the square grid that consist of $n-1$ unit steps.
We explain possible connections between the poset Tam$(v)$ and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.
References
- D. Armstrong, Rational Catalan combinatorics 1,2,3,4, available on personal website: http://www.math.miami.edu/ armstrong/activity.html, 2012-2013.
- Drew Armstrong, Nicholas A. Loehr, and Gregory S. Warrington, Rational parking functions and Catalan numbers, Ann. Comb. 20 (2016), no. 1, 21–58. MR 3461934, DOI 10.1007/s00026-015-0293-6
- Drew Armstrong, Brendon Rhoades, and Nathan Williams, Rational associahedra and noncrossing partitions, Electron. J. Combin. 20 (2013), no. 3, Paper 54, 27. MR 3118962, DOI 10.37236/3432
- Francois Bergeron, Adriano Garsia, Emily Sergel Leven, and Guoce Xin, Compositional $(km,kn)$-shuffle conjectures, Int. Math. Res. Not. IMRN 14 (2016), 4229–4270. MR 3556418, DOI 10.1093/imrn/rnv272
- François Bergeron, Algebraic combinatorics and coinvariant spaces, CMS Treatises in Mathematics, Canadian Mathematical Society, Ottawa, ON; A K Peters, Ltd., Wellesley, MA, 2009. MR 2538310, DOI 10.1201/b10583
- 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
- M. T. L. Bizley, Derivation of a new formula for the number of minimal lattice paths from $(0,0)$ to $(km,kn)$ having just $t$ contacts with the line $my=nx$ and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar. 80 (1954), 55–62. MR 61567, DOI 10.1017/S002026810005424X
- Mireille Bousquet-Mélou, Guillaume Chapuy, and Louis-François Préville-Ratelle, The representation of the symmetric group on $m$-Tamari intervals, Adv. Math. 247 (2013), 309–342. MR 3096799, DOI 10.1016/j.aim.2013.07.014
- 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
- F. Chapoton, Sur le nombre d’intervalles dans les treillis de Tamari, Sém. Lothar. Combin. 55 (2005/07), Art. B55f, 18 (French, with English and French summaries). MR 2264942
- Grégory Chatel and Viviane Pons, Counting smaller trees in the Tamari order, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013, pp. 433–444 (English, with English and French summaries). MR 3091011
- Marie-Pierre Delest and Gérard Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984), no. 1-2, 169–206. MR 774044, DOI 10.1016/0304-3975(84)90116-6
- Wenjie Fang and Louis-François Préville-Ratelle, The enumeration of generalized Tamari intervals, European J. Combin. 61 (2017), 69–84. MR 3588709, DOI 10.1016/j.ejc.2016.10.003
- 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, DOI 10.1016/S0021-9800(67)80024-3
- Eugene Gorsky, Mikhail Mazin, and Monica Vazirani, Affine permutations and rational slope parking functions, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), Discrete Math. Theor. Comput. Sci. Proc., AT, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2014, pp. 887–898 (English, with English and French summaries). MR 3466430
- Eugene Gorsky and Andrei Neguţ, Refined knot invariants and Hilbert schemes, J. Math. Pures Appl. (9) 104 (2015), no. 3, 403–435 (English, with English and French summaries). MR 3383172, DOI 10.1016/j.matpur.2015.03.003
- James Haglund, The $q$,$t$-Catalan numbers and the space of diagonal harmonics, University Lecture Series, vol. 41, American Mathematical Society, Providence, RI, 2008. With an appendix on the combinatorics of Macdonald polynomials. MR 2371044, DOI 10.1007/s10711-008-9270-0
- Mark Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), no. 2, 371–407. MR 1918676, DOI 10.1007/s002220200219
- Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), no. 1, 17–76. MR 1256101, DOI 10.1023/A:1022450120589
- Tatsuyuki Hikita, Affine Springer fibers of type $A$ and combinatorics of diagonal coinvariants, Adv. Math. 263 (2014), 88–122. MR 3239135, DOI 10.1016/j.aim.2014.06.011
- Jean-Louis Loday and María O. Ronco, Hopf algebra of the planar binary trees, Adv. Math. 139 (1998), no. 2, 293–309. MR 1654173, DOI 10.1006/aima.1998.1759
- Jean-Louis Loday and María O. Ronco, Order structure on the algebra of permutations and of planar binary trees, J. Algebraic Combin. 15 (2002), no. 3, 253–270. MR 1900627, DOI 10.1023/A:1015064508594
- L.-F. Préville-Ratelle and X. Viennot, An extension of Tamari lattices, FPSAC 2015, Daejeon, Korea (DMTCS) (2015), 133–144.
- 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
- Robert Steinberg, Differential equations invariant under finite reflection groups, Trans. Amer. Math. Soc. 112 (1964), 392–400. MR 167535, DOI 10.1090/S0002-9947-1964-0167535-3
- Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131–146. MR 146227
- X. Viennot, Canopy of binary trees, intervals in associahedra and exclusion model in physics, Workshop: Recent trends in Algebraic and Geometric Combinatorics, ICMAT, Madrid, Nov 2013, slides of the talk at: http://www.xavierviennot.org/xavier/exposes/files/Madrid/nov13v2.pdf.
Additional Information
- Louis-François Préville-Ratelle
- Affiliation: Instituto de Mathemática y Física, Universidad de Talca, 2 norte 685, Talca, Chile
- MR Author ID: 966637
- Email: preville-ratelle@inst-mat.utalca.cl
- Xavier Viennot
- Affiliation: CNRS, LABRI, Université de Bordeaux, Bordeaux, France
- MR Author ID: 178395
- Email: viennot@xavierviennot.org
- Received by editor(s): June 17, 2014
- Received by editor(s) in revised form: August 22, 2015, August 27, 2015, and June 20, 2016
- Published electronically: March 17, 2017
- Additional Notes: The first author was supported by the government of Chile under Proyecto Fondecyt 3140298.
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 5219-5239
- MSC (2010): Primary 06A07
- DOI: https://doi.org/10.1090/tran/7004
- MathSciNet review: 3632566