nLab associahedron

Contents

Context

Combinatorics

Higher algebra

Homotopy theory

homotopy theory, (∞,1)-category theory, homotopy type theory

flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed

models: topological, simplicial, localic, …

see also algebraic topology

Introductions

Definitions

Paths and cylinders

Homotopy groups

Basic facts

Theorems

Contents

Idea

The associahedra or Stasheff polytopes {K n}\{K_n\} are CW complexes that naturally arrange themselves into a topological operad that resolves the standard associative operad: an A-infinity-operad.

The vertices of K nK_n correspond to ways in which one can bracket a product of nn variables. The edges correspond to rebracketings, the faces relate different sequences of rebracketings that lead to the same result, and so on.

The associahedra were introduced by Jim Stasheff in order to describe topological spaces equipped with a multiplication operation that is associative up to every higher coherent homotopy.

Definition

Here is the rough idea, copied, for the moment, verbatim from Markl94 p. 26 (for more details see references below):

For n1n \geq 1 the associahedron K nK_n is an (n2)(n-2)-dimensional polyhedron whose ii-dimensional cells are, for 0in20 \leq i \leq n-2, indexed by all (meaningful) insertions of (ni2)(n-i-2) pairs of brackets between nn independent indeterminates, with suitably defined incidence maps.

Simplicially{ } subdivided associahedra (complete with simplicial operadic structure) can be presented efficiently in terms of an abstract bar construction. Let 𝒪:Set/Set/\mathcal{O}: Set/\mathbb{N} \to Set/\mathbb{N} be the monad which takes a graded set XX to the non-permutative non-unital operad freely generated by XX, with monad multiplication denoted m:𝒪𝒪𝒪m: \mathcal{O}\mathcal{O} \to \mathcal{O}. Let t +t_+ be the graded set {X n} n0\{X_n\}_{n \geq 0} that is empty for n=0,1n = 0, 1 and terminal for n2n \geq 2; this carries a unique non-unital non-permutative operad structure, via a structure map α:𝒪t +t +\alpha: \mathcal{O}t_+ \to t_+. The bar construction B(𝒪,𝒪,t +)B(\mathcal{O}, \mathcal{O}, t_+) is an (augmented) simplicial graded set (an object in Set Δ op×Set^{\Delta^{op} \times \mathbb{N}}) whose face maps take the form

𝒪𝒪𝒪t +𝒪𝒪α𝒪mt +m𝒪t +𝒪𝒪t +𝒪αmt +𝒪t +αt +.\ldots \mathcal{O}\mathcal{O}\mathcal{O}t_+ \stackrel{\stackrel{\overset{m\mathcal{O} t_+}{\to}}{\underset{\mathcal{O}m t_+}{\to}}}{\underset{\mathcal{O}\mathcal{O}\alpha}{\to}} \mathcal{O}\mathcal{O}t_+ \stackrel{\overset{m t_+}{\to}}{\underset{\mathcal{O}\alpha}{\to}} \mathcal{O}t_+ \stackrel{\alpha}{\to} t_+.

Intuitively, the (graded set of) 00-cells 𝒪t +\mathcal{O}t_+ consists of planar trees where each inner node has two or more incoming edges, with trees graded by number of leaves; the extreme points are binary trees [corresponding to complete binary bracketings of words], whereas other trees are barycenters of higher-dimensional faces of Stasheff polytopes. The construction B(𝒪,𝒪,t +)B(\mathcal{O}, \mathcal{O}, t_+) carries a simplicial (non-permutative non-unital) operad structure, where the geometric realization of the simplicial set at grade (or arity) nn defines the barycentric subdivision of the Stasheff polytope K nK_n. As the operad structure on B(𝒪,𝒪,t +)B(\mathcal{O}, \mathcal{O}, t_+) is expressed in finite product logic and geometric realization preserves finite products, the (simplicially subdivided) associahedra form in this way the components of a topological operad.

Loday’s realization

Jean-Louis Loday gave a simple formula for realizing the Stasheff polytopes as a convex hull of integer coordinates in Euclidean space (Loday 2004). Let Y nY_n denote the set of (rooted planar) binary trees with n+1n+1 leaves (and hence nn internal vertices). For any binary tree tY nt \in Y_n, enumerate the leaves by left-to-right order, denoted 1,, n+1\ell_1, \ldots, \ell_{n+1}, and enumerate the internal vertices as v 1,,v nv_1, \ldots, v_n where v iv_i is the closest common ancestor of i\ell_i and i+1\ell_{i+1}. Define a vector M(t) nM(t) \in \mathbb{R}^n whose iith coordinate is the product a ib ia_i b_i of the number a ia_i of leaves that are left descendants of v iv_i and the number b ib_i of leaves that are right descendants of v iv_i.

Theorem (Loday)

The convex hull of the points {M(t) ntY n}\{ M(t) \in \mathbb{R}^n \mid t \in Y_n \} is a realization of the Stasheff polytope of dimension n1n-1, and is included in the affine hyperplane {(x 1,,x n):x 1++x n=(n2)}\{(x_1, \ldots, x_n): x_1 + \ldots + x_n = \binom{n}{2}\}.

Illustrations

  • K 1K_1 is the empty set, a degenerate case not usually considered.

  • K 2K_2 is simply the shape of a binary operation:

    xy, x \otimes y ,

    which we interpret here as a single point.

  • K 3K_3 is the shape of the usual associator or associative law

    (xy)zx(yz), (x \otimes y) \otimes z \to x \otimes (y \otimes z) ,

    consisting of a single interval.

  • K 4K_4 The fourth associahedron K 4K_4 is the pentagon which expresses the different ways a product of four elements may be bracketed

One can also think of this as the top-level structure of the 4th oriental. This controls in particular the pentagon identity in the definition of monoidal category, as discussed there.


(image from the Wikimedia Commons)

  • One can rotate and explore Stasheff polyhedra in this interactive associahedron app.

  • Illustrations of some polytopes, including K 5K_5, can also be found here.

  • A template which can be cut out and assembled into a K 5K_5 can be found in Appendix B of ChengLauda2004.

Relation to other structures

Relation to orientals

The above list shows that the first few Stasheff polytopes are nothing but the first few orientals. This doesn’t remain true as nn increases. The orientals are free strict omega-categories on simplexes as parity complexes. This means that certain interchange cells (e.g., Gray tensorators) show up as thin in the oriental description.

The first place this happens is the sixth oriental: where there are three tensorator squares and six pentagons in Stasheff’s K 5K_5, the corresponding tensorator squares coming from O(5)O(5) are collapsed.

It was when Todd Trimble made this point to Ross Street that Street began to think about using associahedra to define weak n-categories.

Categorified associahedra

There is a categorification of associahedra discussed in

  • S. Saneblidze, R. Umble, Diagonals on the permutahedra, multiplihedra and associahedra, Homology Homotopy Appl. 6(1) (2004) 363–411.
  • Stefan Forcey, Quotients of the multiplihedron as categorified associahedra, Homology Homotopy Appl. 10:2 (2008) 227–256 (Euclid)

Tamari lattice

The associahedron is closely related to a structure known as the Tamari lattice, which is especially well-studied in combinatorics. The Tamari lattice T nT_n can be defined as the poset of all parenthesizations of n+1n+1 variables with the order generated by rightwards reassociation (ab)ca(bc)(a b)c \le a(b c), or equivalently as the poset of all binary trees with nn internal nodes (and hence n+1n+1 leaves), with the order generated by rightwards tree rotation. (Note the off-by-one offset from the convention for associahedra: the Tamari lattice T nT_n corresponds to the associahedron K n+1K_{n+1}.) It was originally introduced by Dov Tamari in his thesis “Monoïdes préordonnés et chaînes de Malcev” (Université de Paris, 1951), around a decade before Jim Stasheff’s work.1

As the name suggests, the Tamari lattice also carries the structure of a lattice. This property was originally established by Haya Friedman and Tamari (1967), and later simplified by Samuel Huang and Tamari (1972).

References

The original articles that define associahedra and in which the operad KK that gives A()A(\infty)-topological spaces is implicit are

  • Jim Stasheff, Homotopy associativity of H-spaces I, Trans. Amer. Math. Soc. 108 (1963), 275–312. (web)

  • Jim Stasheff, Homotopy associativity of H-spaces II, Trans. Amer. Math. Soc. 108 (1963), 293–312. (web)

A textbook discussion (slightly modified) is in section 1.6 of the book

Loday’s original article on the Stasheff polytope is

  • Jean-Louis Loday, Realization of the Stasheff polytope, Archiv der Mathematik 83 (2004), 267-278. (doi)

Further explanations and references are collected at

The connection to Tamari lattices as well as other developments are in

  • Folkert Müller-Hoissen, Jean Marcel Pallo, Jim Stasheff (editors), Associahedra, Tamari Lattices, and Related Structures: Tamari Memorial Festschrift, Birkhäuser, 2012. (google books)

For a template of K 5K_5, see Appendix B of the following.

For the combinatorics of associahedra, see

category: combinatorics

  1. Jim Stasheff comments on this in an essay titled “How I ‘met’ Dov Tamari” (Tamari Memorial Festschrift 2012), writing that the “so-called Stasheff polytope … more accurately should be called the Tamari or Tamari-Stasheff polytope”.

Last revised on July 18, 2024 at 19:02:14. See the history of this page for a list of all contributions to it.