Permutohedra and associahedra. (English) Zbl 1401.06003

Grätzer, George (ed.) et al., Lattice theory: special topics and applications. Volume 2. Basel: Birkhäuser/Springer (ISBN 978-3-319-44235-8/pbk; 978-3-319-44236-5/ebook). 215-286 (2016).
This chapter is devoted to two special types of lattices: permutohedra and associahedra.
The permutohedron on \(n\) letters is defined as a certain poset built on the set \(\mathrm{Sym}(n)\) of permutations of \([n] = \{1, 2, \dots, n\}\). For \(\sigma \in \mathrm{Sym}(n)\), the inversion \(\mathrm{inv}(\sigma)\) is the set of pairs \((i,j)\), with \(1 \leq i < j \leq n\), such that \(\sigma^{-1}(i) > \sigma^{-1}(j)\). The ordering relation \(\leq\) on \(\mathrm{Sym}(n)\) is defined by: \(\sigma < \tau\) if and only if \(\mathrm{inv}(\sigma) \subseteq \mathrm{inv}(\tau)\).The poset \(\mathsf{P}(n) = (\mathrm{Sym}(n),\leq)\) is known to be a lattice.
The associahedron (or Tamari lattice) \(\mathbb{A}(n)\) can be defined as the set of all possible binary bracketings on a sequence of \(n+1\) fixed elements. A lattice ordering on \(\mathbb{A}(n)\) is defined as the reflexive, transitive closure of the relation \(\prec\) given by: \(s \prec t\) if and only if \(t\) can be obtained from \(s\) by changing a subword of the form \((uv)w\) to the word \(u(vw)\). The base set of \(\mathbb{A}(n)\) is in one-to-one correspondence with the set of vertices of the Stasheff polytope, also called an associahedron. The word associahedron may also have a broader meaning.
The chapter provides a brief survey on the main lattice properties of permutohedra, Tamari lattices, and related objects such as Cambrian lattices of type \(A\), shows links between them, and provides explicit proofs of some properties and references for the others.
The chapter starts with a very interesting and nicely written introduction concerning the origin of the two concepts, their history and links to some other areas where they appear. Next, the authors provide a number of basic notions (in particular the frequently used notion of clopen sets), notation, terminology and tools involved. They also show that for both concepts, different definitions coming from different approaches can be in fact considered as equivalent.
The main results presented in the chapter include: a characterization of the irreducible elements of permutohedra, a characterization of the join-dependency relation, and a new explicit description of the \(OD\)-graphs of permutohedra, which provide proofs for the semidistributivity of permutohedra and Tamari lattices and their boundedness. The last part discusses connections between permutohedra, Tamari lattices and Cambrian lattices of type \(A\), and various embedding results and problems arising from Grätzer’s 1971 problem of characterizing the sublattices of Tamari lattices. The chapter finishes with an impressive “gallery of lattices” — diagrams of 15 examples of permutohedra and associahedra.
For the entire collection see [Zbl 1357.06001].


06B05 Structure theory of lattices
06A07 Combinatorics of partially ordered sets
52B12 Special polytopes (linear programming, centrally symmetric, etc.)


Zbl 1357.06001
Full Text: DOI


[1] pp.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.