Geometry of $\nu$-Tamari lattices in types $A$ and $B$
HTML articles powered by AMS MathViewer
- by Cesar Ceballos, Arnau Padrol and Camilo Sarmiento PDF
- Trans. Amer. Math. Soc. 371 (2019), 2575-2622
Abstract:
In this paper, we exploit the combinatorics and geometry of triangulations of products of simplices to derive new results in the context of Catalan combinatorics of $\nu$-Tamari lattices. In our framework, the main role of “Catalan objects” is played by $(I,\overline {J})$-trees: bipartite trees associated to a pair $(I,\overline {J})$ of finite index sets that stand in simple bijection with lattice paths weakly above a lattice path $\nu =\nu (I,\overline {J})$. Such trees label the maximal simplices of a triangulation whose dual polyhedral complex gives a geometric realization of the $\nu$-Tamari lattice introduced by Prévile-Ratelle and Viennot. In particular, we obtain geometric realizations of $m$-Tamari lattices as polyhedral subdivisions of associahedra induced by an arrangement of tropical hyperplanes, giving a positive answer to an open question of F. Bergeron.
The simplicial complex underlying our triangulation endows the $\nu$-Tamari lattice with a full simplicial complex structure. It is a natural generalization of the classical simplicial associahedron, an alternative to the rational associahedron of Armstrong, Rhoades, and Williams, whose $h$-vector entries are given by a suitable generalization of the Narayana numbers.
Our methods are amenable to cyclic symmetry, which we use to present type $B$ analogues of our constructions. Notably, we define a partial order that generalizes the type $B$ Tamari lattice, introduced independently by Thomas and Reading, along with corresponding geometric realizations.
References
- Federico Ardila and Mike Develin, Tropical hyperplane arrangements and oriented matroids, Math. Z. 262 (2009), no. 4, 795–816. MR 2511751, DOI 10.1007/s00209-008-0400-z
- 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
- Christos A. Athanasiadis, On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Amer. Math. Soc. 357 (2005), no. 1, 179–196. MR 2098091, DOI 10.1090/S0002-9947-04-03548-2
- Christos A. Athanasiadis and Eleni Tzanaki, On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. 23 (2006), no. 4, 355–375. MR 2236611, DOI 10.1007/s10801-006-8348-8
- François Bergeron, Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices, Preprint, Mar. 2012, arXiv:1202.6269.
- 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
- L. J. Billera, R. Cushman, and J. A. Sanders, The Stanley decomposition of the harmonic oscillator, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 375–393. MR 976522
- Raoul Bott and Clifford Taubes, On the self-linking of knots, J. Math. Phys. 35 (1994), no. 10, 5247–5287. Topology and physics. MR 1295465, DOI 10.1063/1.530750
- 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
- Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento, Dyck path triangulations and extendability, J. Combin. Theory Ser. A 131 (2015), 187–208. MR 3291480, DOI 10.1016/j.jcta.2014.10.009
- Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento, Geometry of $\nu$-Tamari lattices in types $A$ and $B$, axXiv:1611.09794 (2016)
- Cesar Ceballos, Francisco Santos, and Günter M. Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica 35 (2015), no. 5, 513–551. MR 3437894, DOI 10.1007/s00493-014-2959-9
- 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
- Frédéric Chapoton, Sergey Fomin, and Andrei Zelevinsky, Polytopal realizations of generalized associahedra, Canad. Math. Bull. 45 (2002), no. 4, 537–566. Dedicated to Robert V. Moody. MR 1941227, DOI 10.4153/CMB-2002-054-1
- Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
- Mike Develin and Bernd Sturmfels, Tropical convexity, Doc. Math. 9 (2004), 1–27. MR 2054977
- The Sage Developers, Sagemath, the Sage Mathematics Software System (Version 7.2), 2016, http://www.sagemath.org.
- Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Realizing Simion’s type $B$ associahedron as a pulling triangulation of the Legendre polytope, Sém. Lothar. Combin. 78B (2017), Art. 32, 12 (English, with English and French summaries). MR 3678614
- 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
- Alex Fink and Felipe Rincón, Stiefel tropical linear spaces, J. Combin. Theory Ser. A 135 (2015), 291–331. MR 3366480, DOI 10.1016/j.jcta.2015.06.001
- Sergey Fomin and Nathan Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Not. 44 (2005), 2709–2757. MR 2181310, DOI 10.1155/IMRN.2005.2709
- Sergey Fomin and Andrei Zelevinsky, Cluster algebras. I. Foundations, J. Amer. Math. Soc. 15 (2002), no. 2, 497–529. MR 1887642, DOI 10.1090/S0894-0347-01-00385-X
- Sergey Fomin and Andrei Zelevinsky, Cluster algebras. II. Finite type classification, Invent. Math. 154 (2003), no. 1, 63–121. MR 2004457, DOI 10.1007/s00222-003-0302-y
- Sergey Fomin and Andrei Zelevinsky, $Y$-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977–1018. MR 2031858, DOI 10.4007/annals.2003.158.977
- Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43–73. MR 1785292
- Israel M. Gelfand, Mark I. Graev, and Alexander Postnikov, Combinatorics of hypergeometric functions associated with positive roots, The Arnold-Gelfand mathematical seminars, Birkhäuser Boston, Boston, MA, 1997, pp. 205–221. MR 1429893, DOI 10.1007/978-1-4612-4122-5_{1}0
- I. M. Gel’fand, A. V. Zelevinskiĭ, and M. M. Kapranov, Newton polytopes of principal $A$-determinants, Soviet Math. Doklady 40 (1990), 278–281.
- I. M. Gel’fand, A. V. Zelevinskiĭ, and M. M. Kapranov, Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Leningrad Math. J. 2 (1991), 449–505.
- Mark Haiman, Constructing the associahedron, unpublished manuscript, MIT 1984, 11 pages; math.berkeley.edu/~mhaiman/ftp/assoc/manuscript.pdf.
- Christophe Hohlweg and Carsten E. M. C. Lange, Realizations of the associahedron and cyclohedron, Discrete Comput. Geom. 37 (2007), no. 4, 517–543. MR 2321739, DOI 10.1007/s00454-007-1319-6
- 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
- Birkett Huber, Jörg Rambau, and Francisco Santos, The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings, J. Eur. Math. Soc. (JEMS) 2 (2000), no. 2, 179–198. MR 1763304, DOI 10.1007/s100970050003
- Michael Joswig and Katja Kulas, Tropical and ordinary convexity combined, Adv. Geom. 10 (2010), no. 2, 333–352. MR 2629819, DOI 10.1515/ADVGEOM.2010.012
- Carl W. Lee, The associahedron and triangulations of the $n$-gon, European J. Combin. 10 (1989), no. 6, 551–560. MR 1022776, DOI 10.1016/S0195-6698(89)80072-1
- Jean-Louis Loday, Realization of the Stasheff polytope, Arch. Math. (Basel) 83 (2004), no. 3, 267–278. MR 2108555, DOI 10.1007/s00013-004-1026-y
- 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
- Martin Markl, Simplex, associahedron, and cyclohedron, Higher homotopy structures in topology and mathematical physics (Poughkeepsie, NY, 1996) Contemp. Math., vol. 227, Amer. Math. Soc., Providence, RI, 1999, pp. 235–265. MR 1665469, DOI 10.1090/conm/227/03259
- Karola Mészáros, Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc. 363 (2011), no. 8, 4359–4382. MR 2792991, DOI 10.1090/S0002-9947-2011-05265-7
- Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff (eds.), Associahedra, Tamari lattices and related structures, Progress in Mathematics, vol. 299, Birkhäuser/Springer, Basel, 2012. Tamari memorial Festschrift. MR 3235205, DOI 10.1007/978-3-0348-0405-9
- J-C Novelli and J-Y Thibon, Hopf algebras of m-permutations,(m+ 1)-ary trees, and m-parking functions, arXiv:1403.5962 (2014).
- Jean-Christophe Novelli, m-dendriform algebras, arXiv:1406.1616 (2014).
- T. Kyle Petersen, Pavlo Pylyavskyy, and David E. Speyer, A non-crossing standard monomial theory, J. Algebra 324 (2010), no. 5, 951–969. MR 2659207, DOI 10.1016/j.jalgebra.2010.05.001
- Vincent Pilaud and Christian Stump, Brick polytopes of spherical subword complexes and generalized associahedra, Adv. Math. 276 (2015), 1–61. MR 3327085, DOI 10.1016/j.aim.2015.02.012
- Alexander Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN 6 (2009), 1026–1106. MR 2487491, DOI 10.1093/imrn/rnn153
- Louis-François Préville-Ratelle and Xavier Viennot, The enumeration of generalized Tamari intervals, Trans. Amer. Math. Soc. 369 (2017), no. 7, 5219–5239. MR 3632566, DOI 10.1090/tran/7004
- Nathan Reading, Lattice congruences, fans and Hopf algebras, J. Combin. Theory Ser. A 110 (2005), no. 2, 237–273. MR 2142177, DOI 10.1016/j.jcta.2004.11.001
- Nathan Reading, Cambrian lattices, Adv. Math. 205 (2006), no. 2, 313–353. MR 2258260, DOI 10.1016/j.aim.2005.07.010
- Nathan Reading, From the Tamari lattice to Cambrian lattices and beyond, Associahedra, Tamari lattices and related structures, Progr. Math., vol. 299, Birkhäuser/Springer, Basel, 2012, pp. 293–322. MR 3221544, DOI 10.1007/978-3-0348-0405-9_{1}5
- Nathan Reading and David E. Speyer, Cambrian fans, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 2, 407–447. MR 2486939, DOI 10.4171/JEMS/155
- Rodica Simion, A type-B associahedron, Adv. in Appl. Math. 30 (2003), no. 1-2, 2–25. Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001). MR 1979780, DOI 10.1016/S0196-8858(02)00522-5
- Günter Rote, Francisco Santos, and Ileana Streinu, Expansive motions and the polytope of pointed pseudo-triangulations, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 699–736. MR 2038499, DOI 10.1007/978-3-642-55566-4_{3}3
- Francisco Santos, Christian Stump, and Volkmar Welker, Noncrossing sets and a Graßmann associahedron, 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. 609–620 (English, with English and French summaries). MR 3466407
- Camilo Sarmiento, Camilo Sarmiento’s webpage, http://www.math.uni-leipzig.de/~sarmiento/, Accessed: March 6, 2017.
- Steven Shnider and Shlomo Sternberg, Quantum groups, Graduate Texts in Mathematical Physics, II, International Press, Cambridge, MA, 1993. From coalgebras to Drinfel′d algebras; A guided tour. MR 1287162
- Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23. MR 824105, DOI 10.1007/BF02187680
- Richard P. Stanley and Jim Pitman, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (2002), no. 4, 603–634. MR 1902680, DOI 10.1007/s00454-002-2776-6
- James D. Stasheff, Homotopy associativity of $H$-spaces, Transactions Amer. Math. Soc. 108 (1963), 275–292.
- Salvatore Stella, Polyhedral models for generalized associahedra via Coxeter elements, J. Algebraic Combin. 38 (2013), no. 1, 121–158. MR 3070123, DOI 10.1007/s10801-012-0396-7
- Dov Tamari, Monoïdes préordonnés et chaînes de Malcev, Université de Paris, Paris, 1951 (French). Thèse. MR 0051833
- Hugh Thomas, Tamari lattices and noncrossing partitions in type $B$, Discrete Math. 306 (2006), no. 21, 2711–2723. MR 2263728, DOI 10.1016/j.disc.2006.05.027
- W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249–271. MR 146823, DOI 10.4153/CJM-1963-029-x
- Eleni Tzanaki, Polygon dissections and some generalizations of cluster complexes, J. Combin. Theory Ser. A 113 (2006), no. 6, 1189–1198. MR 2244140, DOI 10.1016/j.jcta.2005.08.010
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
Additional Information
- Cesar Ceballos
- Affiliation: Faculty of Mathematics, University of Vienna, Vienna, Austria
- MR Author ID: 990795
- Arnau Padrol
- Affiliation: Sorbonne Universités, Université Pierre et Marie Curie (Paris 6), Institut de Mathématiques de Jussieu - Paris Rive Gauche (UMR 7586), Paris, France
- Address at time of publication: Sorbonne Université, Institut de Mathématiques de Jussieu - Paris Rive Gauche (UMR 7586), Paris, France
- MR Author ID: 1046332
- Camilo Sarmiento
- Affiliation: Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany
- Address at time of publication: Universidad del Norte, Departamento de Matemáticas y Estadística
- MR Author ID: 1033636
- Received by editor(s): March 9, 2017
- Received by editor(s) in revised form: August 31, 2017, and September 12, 2017
- Published electronically: November 27, 2018
- Additional Notes: The research of the first author was supported by the Austrian Science Foundation FWF, grant F 5008-N15, in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.
The second author was supported by the grant ANR-17-CE40-0018 of the French National Research Agency ANR (project CAPPS) and the program PEPS Jeunes Chercheur-e-s 2016 and 2017 from the INSMI
The third author was partially supported by CDS Magdeburg. - © Copyright 2018 Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento
- Journal: Trans. Amer. Math. Soc. 371 (2019), 2575-2622
- MSC (2010): Primary 05E45, 05E10, 52B22
- DOI: https://doi.org/10.1090/tran/7405
- MathSciNet review: 3896090