Tropical Linear Spaces in Phylogenetics

One approach to phylogenetic tree reconstruction seeks an ultrametric (i.e. equidistant tree metric) that is l-infinity nearest to a given dissimilarity map. While the l-infinity nearest ultrametric is generally not unique, the set of all l-infinity nearest ultrametrics is a tropical polytope. We give an algorithm to compute a superset of its tropical vertices. Ardila and Klivans showed that the set of all ultrametrics on a finite set of size $n$ is the Bergman fan associated to the matroid underlying the complete graph on $n$ vertices. Therefore, we derive our results in the more general context of Bergman fans of matroids. This generality allows our algorithm to be applied to dissimilarity maps where only a subset of the entries are known.