Subdominant Matroid Ultrametrics

Federico Ardila

Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley, CA 94720-5070,
USA

federico@microsoft.com

Annals of Combinatorics 8 (4) p.379-389 December, 2004

Abstract:

Given a matroid *M* on the ground set *E*, the Bergman fan
, or space of *M*-ultrametrics,
is a polyhedral complex in
which arises in several different areas, such as tropical algebraic geometry, dynamical
systems, and phylogenetics. Motivated by the phylogenetic situation, we study the
following problem: Given a point w in
, we wish to find an *M*-ultrametric
which is closest to it in the

The solution to this problem follows easily from the existence of the subdominant*M*-ultrametric: a componentwise maximum *M*-ultrametric which is componentwise
smaller than w. A procedure for computing it is given, which brings together the
points of view of matroid theory and tropical geometry.

When the matroid in question is the graphical matroid of the complete graph*K*_{n}, the Bergman
fan
parameterizes the equidistant phylogenetic trees with n leaves. In this case, our
results provide a conceptual explanation for Chepoi and Fichet's method for computing
the tree that most closely matches measured data.

The solution to this problem follows easily from the existence of the subdominant

When the matroid in question is the graphical matroid of the complete graph

References:

1. F. Ardila and C. Klivans, The Bergman complex of a matroid and phylogenetic trees, arxiv: math.CO/0311370, preprint, 2003.

2. G. Bergman, The logarithmic limit-set of an algebraic variety, Trans. Amer. Math. Soc. 157 (1971) 459--469.

3. R. Bieri and J. Groves, The geometry of the set of characters induced by valuations, J. Reine Angew. Math. 347 (1984) 168--195.

4. L. Billera, S. Holmes, and K. Vogtmann, Geometry of the space of phylogenetic trees, Adv. in Appl. Math. 27 (2001) 733--767.

5. A. Björner, The homology and shellability of matroids and geometric lattices, In: Matroid Applications, N. White, Ed., Cambridge University Press, Cambridge, 1992, pp. 226--283.

6. V. Chepoi and B. Fichet,
ℓ_{∞}-approximation via subdominants,
J. Math. Psych. 44 (2000) 600--616.

7. M. Develin and B. Sturmfels, Tropical convexity, arXiv: math. MG/0308254, preprint, 2003.

8. M. Einsiedler, M. Kapranov, and D. Lind, Non-archimedean amoebas and tropical varieties, arXiv: math. AG/0408311, preprint, 2004.

9. D. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1991.

10. J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.

11. C. Semple and M. Steel, Phylogenetics, Oxford University Press, 2003.

12. B. Sturmfels, Solving Systems of Polynomial Equations, American Mathematical Society, Providence, 2002.

13. D. Speyer and B. Sturmfels, The tropical Grassmannian, arXiv:math.AG/0304218, preprint, 2003.

14. R.E. Tarjan, Data Structures and Network Algorithms, Society of Industrial and Applied Mathematics, 1983.