2026/02/26 by Sagi Snir, Raphael Yuster · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO
paper · pdf · doi:10.1016/j.dam.2026.02.042
It follows from a classical result of Jordan that every tree with maximum degree at most r containing a vertex set labeled by [n], has a single-edge cut which separates two subsets A,B ⊂ [n] for which min\|A|,|B|\ ≥ (n-1)/r. Motivated by the tree dissimilarity problem in phylogenetics, we consider the case of separating vertex sets of \em several trees: Given k trees with maximum degree at most r, containing a common vertex set labeled by [n], we ask for a single-edge cut in each tree which maximizes min\|A|,|B|\ where A,B ⊂ [n] are separated by the corresponding cut at each tree. Denoting this maximum by f(r,k,n) and considering the limit f(r,k) = limn → ∞ f(r,k,n)/n (which is shown to always exist) we determine that f(r,2)=(1)/(2r) and determine that f(3,3)=(2)/(27), which is already quite intricate. The case r=3 is especially interesting in phylogenetics and our result implies that any two (three) binary phylogenetic trees over n taxa have a split at each tree which separates two taxa sets of order at least n/6 (resp. 2n/27), and these bounds are asymptotically tight.