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

This entry was posted in Combinatorics, Computer Science and Optimization, Convex polytopes and tagged , . Bookmark the permalink.

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

  1. l says:

    very interesting, its good for a Fields!!!

Leave a comment