Metraipolis › archive › dc_ec8021e9cedd

Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees — arXiv:2611.05300

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05300
License (as archived)
CC0-1.0
Archived
2026-11-04T12:49:04.176Z
SHA-256 of the archived text
8c9e1d6b698392b5bc546cf3551160914a33694da193793651413d2a234e2f23
Stable URL of this page
https://metraipolis.com/documento/dc_ec8021e9cedd

How to cite

Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees — arXiv:2611.05300 — arXiv (en), https://arxiv.org/abs/2611.05300 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ec8021e9cedd (Metraipolis archive dc_ec8021e9cedd, sha256 8c9e1d6b698392b5bc546cf3551160914a33694da193793651413d2a234e2f23)
BibTeX
@misc{dcec8021e9cedd,
  title = {Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees — arXiv:2611.05300},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05300},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ec8021e9cedd; sha256 8c9e1d6b698392b5bc546cf3551160914a33694da193793651413d2a234e2f23},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05300. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Computational Geometry (cs.CG) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.05300 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:32:32.061Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).