×

The Bergman complex of a matroid and phylogenetic trees. (English) Zbl 1082.05021

The Bergman complex \({\mathcal B}(M)\) of a matroid \(M\) is a polyhedral complex which arises in algebraic geometry, but which the authors describe purely combinatorially.
The main result of this paper is that, appropriately subdivided, the Bergman complex of a matroid \(M\) is the order complex of the proper part of the lattice of flats \(L_M\) of the matroid. As a corollary, the authors have the Bergman complex \({\mathcal B}(M)\) is homotopy equivalent to a wedge of \((r-2)\)-dimensional spheres, where \(r\) is the rank of \(M\).
The authors show the Bergman fan \(\widetilde {\mathcal B}(K_n)\) of the graphical matroid of the complete graph \(K_n\) is homeomorphic to the space of phylogenetic trees \({\mathcal T}_n \times R\). As a corollary, the authors have that the order complex of the proper part of the partition lattice \(\Pi_n\) is a subdivision of the link of the origin in the coarse subdivision of \({\mathcal T}_n\).

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05C05 Trees
92D15 Problems related to evolution

Software:

TropLi
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Triangle of coefficients from fractional iteration of e^x - 1.

References:

[1] Bergman, G., The logarithmic limit-set of an algebraic variety, Trans. Amer. Math. Soc., 157, 459-469 (1971) · Zbl 0197.17102
[2] Bieri, R.; Groves, J., The geometry of the set of characters induced by valuations, J. Reine Angew. Math., 347, 168-195 (1994) · Zbl 0526.13003
[3] Billera, L.; Holmes, S.; Vogtmann, K., Geometry of the space of phylogenetic trees, Adv. Appl. Math., 27, 733-767 (2001) · Zbl 0995.92035
[4] Björner, A., The homology and shellability of matroids and geometric lattices, (Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40 (1992), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0772.05027
[5] Boardman, J. M., Homotopy structures and the language of trees, Proc. Sympos. Pure Math., 22, 37-58 (1971) · Zbl 0242.55012
[6] Borovik, A.; Gelfand, I.; White, N., Coxeter Matroids (2003), Birkhauser: Birkhauser Boston · Zbl 1050.52005
[7] M. Einsiedler, M. Kapranov, D. Lind, Non-archimedean amoebas and tropical varieties, preprint, arXiv:math.AG/0408311; M. Einsiedler, M. Kapranov, D. Lind, Non-archimedean amoebas and tropical varieties, preprint, arXiv:math.AG/0408311 · Zbl 1115.14051
[8] D. Kozen. The design and analysis of algorithms, Lecture Notes in Computer Science, Springer, Berlin, 1991.; D. Kozen. The design and analysis of algorithms, Lecture Notes in Computer Science, Springer, Berlin, 1991. · Zbl 0743.68006
[9] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press New York · Zbl 0784.05002
[10] M.A. Readdy. The pre-WDVV ring of physics and its topology, Proceedings of The Number Theory and Combinatorics in Physics Conference, Ramanujan J. (2005), to appear.; M.A. Readdy. The pre-WDVV ring of physics and its topology, Proceedings of The Number Theory and Combinatorics in Physics Conference, Ramanujan J. (2005), to appear. · Zbl 1094.13036
[11] Robinson, A.; Whitehouse, S., The tree representation of \(\sigma_{n + 1}\), J. Pure Appl. Algebra, 111, 245-253 (1996) · Zbl 0865.55010
[12] C. Semple, M. Steel, Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2003.; C. Semple, M. Steel, Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2003.
[13] Speyer, D.; Sturmfels, B., The tropical Grassmannian, Adv. Geom., 4, 389-411 (2004) · Zbl 1065.14071
[14] Stanley, R. P., Enumerative Combinatorics, vol. 1 (1986), Cambridge University Press: Cambridge University Press New York · Zbl 0608.05001
[15] Sturmfels, B., Solving systems of polynomial equations, (CBMS Regional Conference Series in Mathematics, vol. 97 (2002), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 1101.13040
[16] Sundaram, S., Homotopy of the non-modular partitions and the Whitehouse module, J. Algebraic Combin., 9, 251-269 (1999) · Zbl 0930.05099
[17] Trappmann, H.; Ziegler, G. M., Shellability of complexes of trees, J. Combin. Theory Ser. A, 82, 168-178 (1998) · Zbl 0916.06004
[18] Vogtmann, K., Local structure of some \(OUT (F_n)\)-complexes, Proc. Edinb. Math. Soc., 33, 2, 367-379 (1990) · Zbl 0694.20021
[19] M. Wachs, Personal communication, 2003.; M. Wachs, Personal communication, 2003.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.