Extreme rays of the ^-nearest ultrametric tropical polytope

DOI10.1016/J.LAA.2019.10.026zbMATH Open1437.92092arXiv1907.10521OpenAlexW2985315234MaRDI QIDQ2174403FDOQ2174403

Luyan Yu

Publication date: 21 April 2020

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

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$.

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)

Cites Work

• Max-linear Systems: Theory and Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of strongly connected components in directed hypergraphs
• \(l_\infty\)-approximation via subdominants.
• Computing the vertices of tropical polyhedra using directed hypergraphs
• The Bergman complex of a matroid and phylogenetic trees
• Title not available (Why is that?)
• The Minkowski theorem for max-plus convex sets
• Title not available (Why is that?)
• Tropical geometric variation of tree shapes
• Tropical principal component analysis and its application to phylogenetics
• L-Infinity Optimization to Bergman Fans of Matroids with an Application to Phylogenetics

Cited In (6)

• Subdominant matroid ultrametrics
• The extreme rays of the \(5 \times 5\) copositive cone
• Tropical convexity
• On matrix semiring over the extended tropical semiring
• L-Infinity Optimization to Bergman Fans of Matroids with an Application to Phylogenetics
• 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)