TBR adjacency implies BME adjacency

Let Tn\mathcal{T}_n be the space of trees on nn leaves. For T,TTnT,T'\in\mathcal{T}_n, let dTBR(T,T)d_{TBR}(T,T') denote the minimum number of tree-bisection-regrafting moves needed to transform TT to TT'. Let dBME(T,T)=1d_{BME}(T,T')=1 when the corresponding vertices wT\mathbf{w}^T and wT\mathbf{w}^{T'} are joined by an edge in the balanced minimum evolution polytope Pn\mathcal{P}_n. TBR adjacency conjecture. If T,TTnT,T'\in\mathcal{T}_n, then

dTBR(T,T)=1d_{TBR}(T,T')=1

implies

dBME(T,T)=1.d_{BME}(T,T')=1.

Nearest-neighbor interchange adjacency implies subtree-prune-regraft adjacency, and subtree-prune-regraft adjacency is known to imply BME adjacency. The paper reports no examples showing that TBR adjacency fails to imply BME adjacency, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

David C. Haws, Terrell Hodge and Ruriko Yoshida, “Optimality of the Neighbor Joining Algorithm and Faces of the Balanced Minimum Evolution Polytope”, arXiv:1004.2073 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.