Ziegler´s Lecture on the Associahedron

Posted on February 28, 2009 by Gil Kalai

j_stasheffdevadoss

 

The associahedron in 3 dimension, and James Stasheff. This picture is taken from Bill Casselman’s article on the associahedron. The article is entitled “Strange Associations” and starts with “There are many other polytopes that can be described in purely combinatorial terms. Among the more curious are the associahedra….”

Dov Tamari as a young student at the Hebrew University of Jerusalem.

The associahedron (also known as the Stasheff polytope) is a remarkable convex polytope first described combinatorially by James Stasheff in 1963. The first proof that it is indeed a polytope is attributed to John Milnor (unpublished). The combinatorial structure was considered independently by Dov Tamari who also asked for a realization as a convex polytope, and such a realization was found by Mark Haiman and Carl Lee. It was also constructed independently as a special case of a much more general construction (called ¨secondary polytopes¨) by Israel Gelfand, Michael Kapranov, and Andrei Zelevinsky.

These are lecture notes from Günter M. Ziegler´s lecture on the associahedron at the ¨DocCourse Combinatorics and Geometry 2009¨at CRM located at at the Autonomous University of Barcelona.

 zelevinsky

4.1 Making polytopes from graphs

We will start with several families of graphs and ask if there is a nice cell structure extending the graph structure, and if this cell structure is the cell structure of  a convex polytope. 

4.1.1 Permutations and the permutahedron

Example I:

The vertices: all permutations on the letters 1,2,… ,n

The edges: Two permutations are adjacent if one is obtained by the other by replacing the location of two adjacent letters.

The number of vertices is n!. The degree of every vertex is n-1.

4.1.2 Bracketing and the associahedron

(or triangulation of polygons with non-crossing diagonals, or binary trees)

Example II:

The vertices correspond to all ways to put brackets in an expression x_1x_2\cdots x_n of n non associative variables.

For example for 4 variables there are 5 vertices corresponding to: ((xy)z)u, (x(yz))u, (xy)(zu), x((yz)u), and x(y(zu)).  Those are in one to one correspondence with all possible triangulations of a 5-gon with noncrossing diagonals, as well as with binary trees with 4 leaves.

The edges are obtained by replacing a subword t(su) by (ts)u.

Note: “subword” of course means that t or s or u could be a word, not just a letter.

The number of vertices is the (n-1)-th Catalan number c_{n-1}=\frac{1}{n}{{2n-2} \choose {n-1}}. The degree of every vertex is n-1.

 4.1.3 Bracketing plus cyclic permutations and –  the cyclohedron

Raoul Bott in 1986

  

Example III:

The vertices: This time you consider all ways to put brackets in a word x_1x_2\cdots x_n as in example II and also in all words obtained as cyclic permutations of this word.

The edges: In addition to the same brackets as in example II you also allow changing the order of terms in the ¨top¨multiplication.

For example, when there are four variables we have 20 vertices. In addition to the type of edges we saw in the associahedron there is an edge also between (xy)(zu) to (zu)(xy) and between ((xy)z)u to u((xy)z).  

The number of vertices is n c_{n-1}. The degree of every vertex is n.

4.1.4 Bracketing and all permutations – the permuto-associahedron.

Example IV:

The vertices: This time you consider all ways to put brackets in a word x_1x_2\cdots x_n as in example II and also in all words obtained by arbitrary permutations of this word.

The edges: In addition to the same brackets as in example II you also allow changing the order of two variables which are getting multiplied according to the bracketing. Note: the degree is not constant. The number of additional edges varies between 1 and [n/2].

For example: (xy)(zu) is adjacent to (yx)(zu) and to (xy)(uz) (two additional edges); ((xy)z)u is adjacent to ((yx)z)u. (One additional edge.)

The number of vertices is n! c_{n-1}. The degree of every vertex varies between  n, and n-1+[\frac {n-1}{2}].

 4.1.5 Background

The origin of the permutahedron is not clear to me and is older than the other examples. We talked a little about the origin of the associahedron. The cyclohedron was described as a combinatorial object first in the work of Raoul Bott and Clifford Taubes. The permuto-associahedron (also known as the Kapranotope)  was first described as a combinatorial object by Mikhail Kapranov.

 

4.1.6 An anecdote about Stefan Zweig and Raoul Bott

 

Günter told an interesting story about Raoul Bott (which can be found in Bott’s collected papers). Stefan Zweig met Bott on a transatlantic ship and a there is a character, a tall person with a dream of becoming a mathematician, in Zweig’s  famous novel “Chess story” drawn after Bott. 

4.2 Associahedra via Fiber polytope constructions

4.2.1 Fiber polytopes

Let P,Q be polytopes and let f be a linear projection such that  the image of P is Q.

A section is a map \gamma from Q to P so that f(\gamma (x)) = x for every x \in P.

Let z(\gamma) = (vol (Q))^{-1}\int_Q \gamma(X)dx

The fiber polytope \Sigma(P \to Q) is defined by:  

\Sigma(P \to Q) =\{z(\gamma): \gamma~~ is~~a~~section~ \}.

Fiber polytopes were defined by Lou Billera and Bernd Sturmfels. The case where P is a simplex was already defined by Gelfand, Kapranov, and Zelevinsly. In this case the fiber polytope \Sigma(P \to Q) is called the “secondary polytope” of Q.

4.2.2 Basic properties

a)The fiber polytope is convex, and is a polytope.

b) We need worry in the definition only about piecewise-linear sections.

c) The fiber polytope is a subpolytope of P and it projects to the center of gravity of Q.

d) Its dimension is \dim P - \dim Q.

e) The vertices of the fiber polytopes correspond to special sections which are extreme for a direction in the affine space of Q.

f) The vertices correspond to polyhedral decompositions of Q obtained by certain projections of the facets of Q. 

4.2.2 The permutahedron as a fiber polytope

Take P to be the unit cube [0,1]^n, let Q be the interval [0,n], and let the projection be given by the sum of coordinates. Then the fiber polytope is the permutahedron.

(Remark: I vaguely remember a conjecture from the late ’80s that the permutahedron can also be described as the secondary polytope of a (certain) non-regular cross polytope.)

4.2.3 The associahedron as a fiber polytope

The associahedron is the fiber polytope associated to the projection of the simplex with n vertices to a planar convex polygon with n vertices.

4.2.4 The permutoassociahedron (and the cyclohedron) as generalized fiber polytopes

Vic Reiner and Günter Ziegler had a construction of Kapranov’s permuto-associahedron based on an extension of the fiber polytope idea where the projection is non-linear. (A general theory of such generalized fiber polytopes is not in place yet.) Ziegler found (but did not publish) a fiber-like construction for the cyclohedron based on non-continuous projections.  

 

4.3 Associahedra via root systems constructions

fomin

This is a more recent approach to the associahedron and some extensions by Sergey Fomin and Andrei Zelevinsky which is related to the theory of ¨cluster algebras¨ that they have developed. Günter only briefly discussed it. A basic  fact behind this approach is:

The associahedron is a polytope whose normal to facets are described by all negative roots plus a basis to the positive roots for the root system A_n.  

(Equivalently, the dual polytope is described by the convex hull of a certain scaling of the set of roots just described.)

For the root-system B_n a similar construction gives the cyclohedron.

. 

 

 milnor_3

 carlee2

serganova

mat-01 by OhDarkDevil.

 

sleator

ziegler1

Andrei Zelevinsky

 polytope-de-stasheff

Pictures of some participants in the associahedron saga from top to bottom: James Stasheff, Anderi Zelevinsky, Raoul Bott, Mikhail Kapranov, (Stefan Zweig), Vic Reiner, Sergey (Seriushinka) (Seriozhen’ka) Fomin, Israel Gelfand, Bernd Sturmfels, Lou Billera, Clifford Taubes (drawn by Hannibal Taubes) ,  John Milnor, Mark Haiman, Carl Lee (middle), Vera Serganova, Alex Postnikov, Francisco (Pako) Santos, Jean-Louis Loday, Robert Tarjan, William Thurston, Daniel Sleator, Günter Ziegler, one of the above again (guess) and the associahedron again.

This entry was posted in Convex polytopes and tagged , , , . Bookmark the permalink.

8 Responses to Ziegler´s Lecture on the Associahedron

  1. Gil Kalai says:
    March 3, 2009 at 5:45 pm

    Some nice comments on this post (and on Russian diminutives) can be found in Andrei’s blog http://avzel.blogspot.com/2009/03/gil-kalais-notes-on-gunter-zieglers.html

    Reply

  2. Pingback: The Thompson Group « Combinatorics and more

  3. Pingback: Politopos (actualizado2). « US Patent Appl. 12213303: Comentarios.

  4. Comment says:
    August 20, 2010 at 4:03 pm

    You forgot to mention Alexander Postnikov in the list of credits… Nice picture of Günter, though…

    Reply
  5. Gil Kalai says:
    December 30, 2012 at 9:12 am

    A simple proof of the Sleator-Tarjan-Thurston diameter result for the associahedron was found by Lionel Pournin see http://teachingintrotocs.blogspot.co.il/2012/12/the-diameter-of-flip-graph-of.html .

    Reply

  6. Pingback: Lionel Pournin found a combinatorial proof for Sleator-Tarjan-Thurston diameter result | Combinatorics and more

  7. Pingback: Andrei | Combinatorics and more

  8. Pingback: Dubcan Dauvergne and Bálint Virág Settled the Random Sorting Networks Conjectures | Combinatorics and more

Leave a comment