A sharp differing-edge bound for convex plane-tree flips
Let $P \subset \mathbb{R}^2$ be a finite set in strictly convex position, and let $T, T'$ be spanning trees on $P$ whose edges are straight segments, no two edges of the same tree crossing. A flip deletes one edge and inserts another, leaving such a non-crossing spanning tree; the deleted and inserted edges may cross. Write $d_{\mathrm{flip}}(T, T')$ for the minimum number of flips from $T$ to $T'$ and $$\delta(T, T') = |E(T) \setminus E(T')| = \tfrac12 |E(T) \mathbin{\triangle} E(T')|.$$
Always $d_{\mathrm{flip}} \ge \delta$, and $d_{\mathrm{flip}} \le 2\delta$ is easy. Bousquet, De Meyer, Pierron and Wesolek proved $d_{\mathrm{flip}}(T, T') \le \frac{22 + \sqrt2}{12}\, \delta(T, T')$, and constructed, for every $k$ divisible by $3$, pairs with $\delta = k$ that need at least $\tfrac53 k$ flips. Bjerkevik, Kleist, Ueckerdt and Vogtenhuber proved $d_{\mathrm{flip}}(T, T') \le \tfrac53 \delta(T, T') + \tfrac23 b - \tfrac43$ for $|P| \ge 3$, where $b$ is the number of common edges of $T$ and $T'$ on the boundary of the convex hull, and that the flip graph on $n \ge 3$ points has diameter at most $\tfrac53 n - 3$.
Problem. Prove or disprove that every such pair satisfies $$d_{\mathrm{flip}}(T, T') \le \frac53\, \delta(T, T').$$
Source: Bousquet, De Meyer, Pierron and Wesolek (2026), Question 5 (arXiv 2023).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, flip graphs, non-crossing spanning trees
References
@article{bousquet2026reconfiguration,
author = {Bousquet, Nicolas and De Meyer, Lucas and Pierron, Th{\'e}o and Wesolek, Alexandra},
title = {Reconfiguration of Plane Trees in Convex Geometric Graphs},
journal = {Discrete Comput. Geom.},
volume = {75},
number = {2},
year = {2026},
pages = {431--464},
doi = {10.1007/s00454-025-00785-8},
eprint = {2310.18518},
archivePrefix = {arXiv},
}
@inproceedings{bjerkevik2025flipping,
author = {Bjerkevik, H{\aa}vard Bakke and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
title = {Flipping Non-Crossing Spanning Trees},
booktitle = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2025},
pages = {2313--2325},
doi = {10.1137/1.9781611978322.77},
eprint = {2410.23809},
archivePrefix = {arXiv},
}
@misc{aim-convex-tree-difference-bound,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A sharp differing-edge bound for convex plane-tree flips}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/587-convex-tree-difference-bound.md},
note = {Entry 587 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00852, "A sharp differing-edge bound for convex plane-tree flips", clopen.solutions.