Graph Distances in Associahedra

Definitions and mathematical statement

For the standard type $A$ interpretation of an associahedron, let $n\geq 3$ be an integer and let $P_n$ be a convex polygon with $n$ cyclically labelled vertices. A triangulation of $P_n$ is a maximal collection of pairwise noncrossing internal diagonals. Let $\mathcal T_n$ be the set of these triangulations. A flip replaces one diagonal of a triangulation by the other diagonal of the quadrilateral formed by its two incident triangles.

Define the associahedron graph $G_n$ to have vertex set $\mathcal T_n$, with two vertices adjacent exactly when they differ by one flip. For $T,U\in\mathcal T_n$, define \[ d_n(T,U)=\min\left\{k\in{\mathbb{Z}}_{\geq 0}:\exists\,T_0,\ldots,T_k\in\mathcal T_n,\ T_0=T,\ T_k=U,\ T_{i-1}\text{ and }T_i\text{ differ by one flip for }1\leq i\leq k\right\}. \] The graph is connected, so this minimum exists; in particular, $d_n(T,T)=0$. After fixing a boundary edge as a root, triangulations correspond to rooted ordered full binary trees with $n-1$ leaves. A full binary tree has exactly two children at each internal vertex, and a rotation is the local replacement $((A,B),C)\leftrightarrow(A,(B,C))$. Under this correspondence, flip distance equals minimum rotation distance.

Problem. Uniformly for every integer $n\geq 3$ and every pair $T,U\in\mathcal T_n$, determine $d_n(T,U)$. The supplied curated formulation requests an exact structural characterization or an efficient exact algorithm beyond the supplied complexity classification. Neither the required form of a structural characterization nor the meaning of efficiency is specified, so that additional objective remains unresolved as a precise performance requirement.

For context, the original excerpt also discusses graph distance in general polytopes and graph diameter, which in this model is \[ \operatorname{diam}(G_n)=\max_{T,U\in\mathcal T_n}d_n(T,U). \] The curated target concerns individual pair distances. The supplied assessment labels the problem partially solved, states that the diameter is solved, and attributes NP-completeness of flip or rotation distance to a 2026 result. These are supplied literature claims, not independently verified conclusions of this draft. The excerpt does not explicitly specify the associahedron type or the precise decision problem covered by the complexity claim.

Short English statement

Given any two triangulations of the same convex polygon, determine the minimum number of diagonal flips transforming one into the other, equivalently the minimum number of rotations between their corresponding rooted ordered binary trees. The source requests further exact structural or algorithmic understanding, but leaves the desired efficiency and characterization criteria unspecified. Its partially solved status and literature claims are supplied dated assessments.

Sources

• Local UnsolvedMath registry, permanent ID $30006204$, title: Graph Distances in Associahedra; exact source problem code: catalogue entry. The supplied record belongs to the Oberwolfach Reports Open Problems collection, gives proposed year 2025, and identifies no individual proposer.
• Supplied report citation: MFO-RIMS Tandem Workshop: Optimization, Theoretical Computer Science and Algebraic Geometry: Convexity and Beyond (2025), Oberwolfach Reports, pp. 405--450, DOI 10.4171/owr/2025/9. https://doi.org/10.4171/owr/2025/9. The supplied excerpt includes the page marker 427. The record describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labelled "Flip-distance complexity": https://arxiv.org/abs/2602.22874. No authors, article title, or precise theorem statement are supplied in the record.
• Literature assessment dated exactly 2026-08-22: the supplied curation reports that the diameter is solved, that a 2026 primary result establishes NP-completeness of flip or rotation distance, and that a full exact algorithmic characterization remains open. This is supplied dated curation, not independently verified; the record explicitly requests independent verification of time-sensitive status and cited claims. Its listed checked sources are the report and the arXiv link above.