Associahedra, Tamari Lattices, and Related Structures

Tamari Memorial Festschrift

Progress in Mathematics, Vol. 299
Editors: Folkert Müller-Hoissen, Jean Pallo and Jim Stasheff
Birkhäuser, 2012

Summary: Tamari lattices originated from weakenings or reinterpretations of the familar associativity law. This has been the subject of Dov Tamari's thesis at the Sorbonne in Paris in 1951 and the central theme of his subsequent mathematical work. Tamari lattices can be realized in terms of polytopes called associahedra, which in fact also appeared first in Tamari's thesis. By now these beautiful structures have made their appearance in many different areas of pure and applied mathematics, such as algebra, combinatorics, computer science, category theory, geometry, topology, and also in physics. Their interdisciplinary nature provides much fascination and value. On the occasion of Dov Tamari's centennial birthday, this book provides an introduction to topical research related to Tamari's work and ideas. Most of the articles collected in it are written in a way accessible to a wide audience of students and researchers in mathematics and mathematical physics and are accompanied by high quality illustrations.

1. Folkert Müller-Hoissen and Hans-Otto Walther:
   Dov Tamari (formerly Bernhard Teitler)
   Abstract: The life of Dov Tamari is described, including a brief introduction to his mathematical work.
   pp 1-40
2. Carl Maxson:
   On Being a Student of Dov Tamari
   Abstract: I reminisce about being a student of Dov Tamari at the State University of New York at Buffalo in the late 1960's.
   pp 41-44
3. Jim Stasheff:
   How I 'met' Dov Tamari
   Abstract: Although I never met Dov Tamari, neither in person nor electronically, our work had one important intersection - the associahedra. This Festschrift has given me the opportunity to set the record straight: the Stasheff polytope was in fact constructed by Tamari in 1951, a full decade before my version. Here I will indulge in recollections of some of the history of the associahedra, its generalizations and applications. Others in this Festschrift will reveal still other aspects of Tamari's vision, especially in more direct relation to the lattice/poset that bears his name.
   pp 45-63
4. Jean-Louis Loday:
   Dichotomy of the Addition of Natural Numbers
   Abstract: This is an elementary presentation of the arithmetic of trees. We show how it is related to the Tamari poset. In the last part we investigate various ways of realizing this poset as a polytope (associahedron), including one inferred from Tamari's thesis.
   pp 65-79
   preprint: arXiv:1108.6238
5. Susan H. Gensemer:
   Partial Groupoid Embeddings in Semigroups
   Abstract: We examine a number of axiom systems guaranteeing the embedding of a partial groupoid into a semigroup. These include the Tamari symmetric partial groupoid and the Gensemer/Weinert equidivisible partial groupoid, provided they satisfy an additional axiom, weak associativity. Both structures share the one mountain property. More embedding results for partial groupoids into other types of algebraic structures are presented as well.
   pp 81-97
6. Satyan L. Devadoss, Benjamin Fehrman, Timothy Heath, and Aditi Vashist:
   Moduli Spaces of Punctured Poincaré Disks
   Abstract: The Tamari lattice and the associahedron provide methods of measuring associativity on a line. The real moduli space of marked curves captures the space of such associativity. We consider a natural generalization by considering the moduli space of marked particles on the Poincaré disk, extending Tamari's notion of associativity based on nesting. A geometric and combinatorial construction of this space is provided, which appears in Kontsevich's deformation quantization, Voronov's swiss-cheese operad, and Kajiura and Stasheff's open-closed string theory.
   pp 99-117
   preprint: arXiv:1109.2830
7. Cesar Ceballos and Günter M. Ziegler:
   Realizing the Associahedron: Mysteries and Questions
   Abstract: There are many open problems and some mysteries connected to the realizations of the associahedra as convex polytopes. In this note, we describe three -- concerning special realizations with the vertices on a sphere, the space of all possible realizations, and possible realizations of the multiassociahedron.
   pp 119-127
   preprint: arXiv:1110.4059
8. Christophe Hohlweg:
   Permutahedra and Associahedra
   Abstract: Permutahedra are a class of convex polytopes arising naturally from the study of finite reflection groups, while generalized associahedra are a class of polytopes indexed by finite reflection groups. We present the intimate links those two classes of polytopes share.
   pp 129-159
   preprint: arXiv:1112.3255
9. Victor M. Buchstaber and Vadim D. Volodin:
   Combinatorial 2-truncated Cubes and Applications
   Abstract: We study a class of simple polytopes, called 2-truncated cubes. These polytopes have remarkable properties and, in particular, satisfy Gal's conjecture. Well-known polytopes (flag nestohedra, graph-associahedra and graph-cubeahedra) are 2-truncated cubes.
   pp 161-186
10. Stefan Forcey:
    Extending the Tamari Lattice to Some Compositions of Species
    Abstract: An extension of the Tamari lattice to the multiplihedra is discussed, along with projections to the composihedra and the Boolean lattice. The multiplihedra and composihedra are sequences of polytopes that arose in algebraic topology and category theory. Here we describe them in terms of the composition of combinatorial species. We define lattice structures on their vertices, indexed by painted trees, which are extensions of the Tamari lattice and projections of the weak order on the permutations. The projections from the weak order to the Tamari lattice and the Boolean lattice are shown to be different from the classical ones. We review how lattice structures often interact with the Hopf algebra structures, following Aguiar and Sottile who discovered the applications of M\"obius inversion on the Tamari lattice to the Loday-Ronco Hopf algebra.
    pp 187-210
    preprint: arXiv:1109.6687
11. Patrick Dehornoy:
    Tamari Lattices and the Symmetric Thompson Monoid
    Abstract: We investigate the connection between Tamari lattices and the Thompson group F, summarized in the fact that F is a group of fractions for a certain monoid F⁺_sym whose Cayley graph includes all Tamari lattices. Under this correspondence, the Tamari lattice meet and join are the counterparts of the least common multiple and greatest common divisor operations in F⁺_sym. As an application, we show that, for every n, there exists a length ℓ chain in the nth Tamari lattice whose endpoints are at distance at most 12ℓ/n.
    pp 211-250
    preprint: arXiv:1109.5296
12. Ross Street:
    Parenthetic Remarks
    Abstract: The Tamari lattice provides an example of a (non-symmetric) operad. We discuss such operads and their associated monads and monoidal categories. Freeness is an important aspect. The free structures are described in various ways using well-formed words (in the spirit of some of Tamari's papers), using string diagrams leading to forests, and in terms of rewrite rules.
    pp 251-268
13. Frédéric Chapoton:
    On the Categories of Modules over the Tamari Posets
    Abstract: One can attach an Abelian category to each Tamari poset, the category of modules over its incidence algebra. This can also be described as the category of modules over the Hasse diagram of the poset, seen as a quiver with relations. The derived category of this category seems to be a very interesting object, with nice properties and many different descriptions. We recall known results and present some conjectures on these derived categories.
    pp 269-280
14. Hugh Thomas:
    The Tamari Lattice as it Arises in Quiver Representations
    Abstract: In this chapter, we explain how the Tamari lattice arises in the context of the representation theory of quivers, as the poset whose elements are the torsion classes of a directed path quiver, with the order relation given by inclusion.
    pp 281-291
15. Nathan Reading:
    From the Tamari lattice to Cambrian Lattices and Beyond
    Abstract: We trace the path from the Tamari lattice, via lattice congruences of the weak order, to the definition of Cambrian lattices in the context of finite Coxeter groups, and onward to the construction of Cambrian fans. We then present sortable elements, the key combinatorial tool for studying Cambrian lattices and fans. The chapter concludes with a brief description of the applications of Cambrian lattices and sortable elements to Coxeter-Catalan combinatorics and to cluster algebras.
    pp 293-322
    preprint: arXiv:1109.5105
16. Filippo Disanto, Luca Ferrari, Renzo Pinzani, Simone Rinaldi:
    Catalan Lattices on Series Parallel Interval Orders
    Abstract: Using the notion of series parallel interval order, we propose a unified setting to describe Dyck lattices and Tamari lattices (two well-known lattice structures on Catalan objects) in terms of basic notions of the theory of posets. As a consequence of our approach, we find an extremely simple proof of the fact that the Dyck order is a refinement of the Tamari one. Moreover, we provide a description of both the weak and the strong Bruhat order on 312-avoiding permutations, by recovering the proof of the fact that they are isomorphic to the Tamari and the Dyck order, respectively; our proof, which simplifies the existing ones, relies on our results on series parallel interval orders.
    pp 323-338
17. Maria Ronco:
    Generalized Tamari Order
    Abstract: In their paper "Coxeter complexes and graph associahedra", Topology and its Applications 153 (2006) 2155-2168, M. Carr and S. Devadoss introduced the notion of tubing on a finite simple graph G. When G is the linear graph L_n, with n vertices, the polytope KL_n is the Stasheff polytope or associahedron. Our goal is to describe a partial order on the set of tubings of a simple graph, which generalizes the Tamari order on the set of vertices of the associahedron. For certain families of graphs, this order induces an associative product on the vector space spanned by the tubings of all the graphs.
    pp 339-350
18. Jörg Rambau and Victor Reiner:
    A Survey of the Higher Stasheff-Tamari Orders
    Abstract: The Tamari lattice, thought as a poset on the set of triangulations of a convex polygon with n vertices, generalizes to the higher Stasheff-Tamari orders on the set of triangulations of a cyclic d-dimensional polytope having n vertices. This survey discusses what is known about these orders, and what one would like to know about them.
    pp 351-390
19. Aristophanes Dimakis and Folkert Müller-Hoissen:
    KP Solitons, Higher Bruhat and Tamari Orders
    Abstract: In a tropical approximation, any tree-shaped line soliton solution, a member of the simplest class of soliton solutions of the Kadomtsev-Petviashvili (KP-II) equation, determines a chain of planar rooted binary trees, connected by right rotation. More precisely, it determines a maximal chain of a Tamari lattice. We show that an analysis of these solutions naturally involves higher Bruhat and higher Tamari orders.
    pp 391-423
    preprint: arXiv:1110.3507
20. Appendix: Dov Tamari's Publications
    pp 425-428