The diameter of associahedra
arXiv:1207.6296 · doi:10.1016/j.aim.2014.02.035
Abstract
It is proven here that the diameter of the d-dimensional associahedron is 2d-4 when d is greater than 9. Two maximally distant vertices of this polytope are explicitly described as triangulations of a convex polygon, and their distance is obtained using combinatorial arguments. This settles two problems posed about twenty-five years ago by Daniel Sleator, Robert Tarjan, and William Thurston.
28 pages, 14 figures, minor improvements
Cited by in corpus (30)
- Associahedra via spines
- Noncrossing sets and a Graßmann associahedron
- Compatibility fans for graphical nested complexes
- The asymptotic diameter of cyclohedra
- The diameter of type D associahedra and the non-leaving-face property
- Celebrating Loday's Associahedron
- Genomic data analysis in tree spaces
- Diameter estimates for graph associahedra
- Graph properties of graph associahedra
- Once punctured disks, non-convex polygons, and pointihedra
- Edge conflicts do not determine geodesics in the associahedron
- Lagrangian Fillings in A-type and their Kalman Loop Orbits
- A logarithmic bound for the chromatic number of the associahedron
- Rectangulotopes
- Eccentricities in the flip-graphs of convex polygons
- Modular flip-graphs of one holed surfaces
- Strong convexity in flip-graphs
- The rotation distance of brooms
- Flip Graphs, Yoke Graphs and Diameter
- Random growth on a Ramanujan graph
- Enumerative problems for arborescences and monotone paths on polytope graphs
- On flips in planar matchings
- Counting difficult tree pairs with respect to the rotation distance problem
- Higher Secondary Polytopes for Two-Dimensional Zonotopes
- Wigglyhedra
- Counting geodesics between surface triangulations
- Pebble trees
- The coarse geometry of hexagon decomposition graphs
- Practical estimation of rotation distance and induced partial order for binary trees
- Graphical zonotopes with the same face vector