Lionel Pournin found a combinatorial proof for Sleator-Tarjan-Thurston diameter result

I just saw in Claire Mathieu’s blog  “A CS professor blog” that a simple proof of the Sleator-Tarjan-Thurston’s diameter result for the graph of the associahedron was found by Lionel Pournin! Here are slides of his lecture “The diameters of associahedra” and link to the paper with the same title “The diameters of associahedra.” The original proof was based on hyperbolic volume computations and was quite difficult. (Here is an earlier post on the associahedron and an earlier mention of a connection found by Dehornoy with the Thompson group.)

Ziegler´s Lecture on the Associahedron

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).  

Continue reading