Uniform semimodular lattices and valuated matroids. (English) Zbl 1414.05066
Summary: In this paper, we present a lattice-theoretic characterization for valuated matroids, which is an extension of the well-known cryptomorphic equivalence between matroids and geometric lattices (= atomistic semimodular lattices). We introduce a class of semimodular lattices, called uniform semimodular lattices, and establish a cryptomorphic equivalence between integer-valued valuated matroids and uniform semimodular lattices. Our result includes a coordinate-free lattice-theoretic characterization of integer points in tropical linear spaces, incorporates the Dress-Terhalle completion process of valuated matroids, and establishes a smooth connection with Euclidean buildings of type A.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 06B99 | Lattices |
Keywords:
valuated matroid; uniform semimodular lattice; geometric lattice; tropical linear space; tight span; Euclidean buildingReferences:
| [1] | Aigner, M., Combinatorial Theory, (1979), Springer: Springer Berlin · Zbl 0415.05001 |
| [2] | Ardila, F.; Klivans, C. J., The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96, 38-49, (2006) · Zbl 1082.05021 |
| [3] | Birkhoff, G., Lattice Theory, (1940), American Mathematical Society: American Mathematical Society New York, 3rd edn., American Mathematical Society, Providence, RI, 1967 · JFM 66.0100.04 |
| [4] | Bruhat, F.; Tits, J., Groupes réductifs sur un corps local, Publ. Math. Inst. Hautes Études Sci., 41, 5-251, (1972) · Zbl 0254.14017 |
| [5] | Develin, M.; Sturmfels, B., Tropical convexity, Doc. Math., 9, 1-27, (2004) · Zbl 1054.52004 |
| [6] | Dress, A.; Kåhrström, J.; Moulton, V., A ‘non-additive’ characterization of ℘-adic norms, Ann. Comb., 15, 37-50, (2011) · Zbl 1271.20042 |
| [7] | Dress, A. W.M.; Terhalle, W., A combinatorial approach to \(p\)-adic geometry, Geom. Dedicata, 46, 127-148, (1993) · Zbl 0777.05038 |
| [8] | Dress, A.; Terhalle, W., The tree of life and other affine buildings, (Proceedings of the International Congress of Mathematicians, Vol. III. Proceedings of the International Congress of Mathematicians, Vol. III, Berlin, 1998. Proceedings of the International Congress of Mathematicians, Vol. III. Proceedings of the International Congress of Mathematicians, Vol. III, Berlin, 1998, Documenta Mathematica Extra Vol. III, (1998)), 565-574 · Zbl 0904.05019 |
| [9] | Dress, A. W.M.; Wenzel, W., Valuated matroids: a new look at the greedy algorithm, Appl. Math. Lett., 3, 33-35, (1990) · Zbl 0701.05014 |
| [10] | Dress, A. W.M.; Wenzel, W., Valuated matroids, Adv. Math., 93, 214-250, (1992) · Zbl 0754.05027 |
| [11] | Garrett, P. B., Building and Classical Groups, (1997), Chapman & Hall: Chapman & Hall London · Zbl 0933.20019 |
| [12] | Hampe, S., Tropical linear spaces and tropical convexity, Electron. J. Combin., 22, Article 4.43, (2015) · Zbl 1330.14099 |
| [13] | Hirai, H., Uniform modular lattice and Euclidean building, (2017), preprint |
| [14] | Hirai, H., Computing degree of determinant via discrete convex optimization on Euclidean building, (2018), preprint |
| [15] | Joswig, M.; Sturmfels, B.; Yu, J., Affine buildings and tropical convexity, Albanian J. Math., 1, 187-211, (2007) · Zbl 1133.52003 |
| [16] | Keel, S.; Tevelev, J., Geometry of Chow quotients of Grassmannians, Duke Math. J., 134, 259-311, (2006) · Zbl 1107.14026 |
| [17] | Maclagan, D.; Sturmfels, B., Introduction to Tropical Geometry, (2015), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1321.14048 |
| [18] | Murota, K., Characterizing a valuated delta-matroid as a family of delta-matroids, J. Oper. Res. Soc. Japan, 40, 565-578, (1997) · Zbl 0905.90144 |
| [19] | Murota, K., Matrices and Matroids for Systems Analysis, (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 0948.05001 |
| [20] | Murota, K., Discrete Convex Analysis, (2003), SIAM: SIAM Philadelphia · Zbl 1029.90055 |
| [21] | Murota, K.; Tamura, A., On circuit valuation of matroids, Adv. in Appl. Math., 26, 192-225, (2001) · Zbl 0979.05028 |
| [22] | Speyer, D. E., Tropical linear spaces, SIAM J. Discrete Math., 22, 1527-1558, (2008) · Zbl 1191.14076 |
| [23] | Speyer, D.; Sturmfels, B., The tropical Grassmannian, Adv. Geom., 4, 389-411, (2004) · Zbl 1065.14071 |
| [24] | Tits, J., Buildings of Spherical Type and Finite BN-Pairs, Lecture Notes in Mathematics, vol. 386, (1974), Springer-Verlag: Springer-Verlag Berlin-New York · Zbl 0295.20047 |
| [25] | Zhang, L., Computing convex hulls in the affine building of \(S L_d\), (2018), preprint |
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.
