Extreme rays of the ^-nearest ultrametric tropical polytope

DOI10.1016/J.LAA.2019.10.026MaRDI QIDQ2174403zbMATH OpenOpenAlexFDO

Authors Luyan Yu

Publication date 21 April 2020

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.10521

zbMATH Keywords

phylogeneticstropical geometryextreme rays

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of tropical geometry (14T90)

Abstract: The set of ultrametrics on $[n]$ nodes that are $el{l}^{i}nfty$-nearest to a given dissimilarity map forms a $(max,+)$ tropical polytope. Previous work of Bernstein has given a superset of the set containing all the phylogenetic trees that are extreme rays of this polytope. In this paper, we show that Bernstein's necessary condition of tropical extreme rays is sufficient only for $n=3$ but not for $ngeq4$. Our proof relies on the exterior description of this tropical polytope, together with the tangent hypergraph techniques for extremality characterization. The sufficiency of the case $n=3$ is proved by explicitly finding all extreme rays through the exterior description. Meanwhile, an inductive construction of counterexamples is given to show the insufficiency for $ngeq4$.

Recommendations

• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Subdominant matroid ultrametrics
• Tropical convexity
• L-infinity optimization to linear spaces and phylogenetic trees
• Tree topologies along a tropical line segment

Cites work

• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• Computing the vertices of tropical polyhedra using directed hypergraphs
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Max-linear systems. Theory and algorithms.
• On the complexity of strongly connected components in directed hypergraphs
• Phylogenetic trees and the tropical geometry of flag varieties
• The Bergman complex of a matroid and phylogenetic trees
• The Minkowski theorem for max-plus convex sets
• Tropical geometric variation of tree shapes
• Tropical mathematics
• Tropical principal component analysis and its application to phylogenetics
• \(l_\infty\)-approximation via subdominants.

Cited in

(6)

• Subdominant matroid ultrametrics
• The extreme rays of the \(5 \times 5\) copositive cone
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Tropical convexity
• On matrix semiring over the extended tropical semiring
• Tropical geometric variation of tree shapes

This page was built for publication: Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174403)