×

zbMATH — the first resource for mathematics

The slack realization space of a matroid. (English) Zbl 1420.52017
Summary: We introduce a new model for the realization space of a matroid, which is obtained from a variety defined by a saturated determinantal ideal, called the slack ideal, coming from the vertex-hyperplane incidence matrix of the matroid. This is inspired by a similar model for the slack realization space of a polytope. We show how to use these ideas to certify non-realizability of matroids, and describe an explicit relationship to the standard Grassmann-Plücker realization space model. We also exhibit a way of detecting projectively unique matroids via their slack ideals by introducing a toric ideal that can be associated to any matroid.

MSC:
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Software:
Macaulay2; Matroids
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G., Oriented Matroids, (1993), Cambridge University Press · Zbl 0773.52001
[2] Bokowski, J.; Sturmfels, B., Computational synthetic geometry, 1355, vi+168 p. pp., (1989), Springer-Verlag, Berlin · Zbl 0683.05015
[3] Chen, J., Matroids: A Macaulay2 package, (2015)
[4] Cox, D. A.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, xvi+646 p. pp., (2015), Springer: Springer, Cham · Zbl 1335.13001
[5] Gordon, G.; Mcnulty, J., Matroids: a geometric introduction, xvi+393 p. pp., (2012), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1253.05002
[6] Gouveia, J.; Macchia, A.; Thomas, R. R.; Wiebe, A., The Slack Realization Space of a Polytope
[7] Gouveia, J.; Parrilo, P. A.; Thomas, R. R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 2, 248-264, (2013) · Zbl 1291.90172
[8] Gouveia, J.; Pashkovich, K.; Robinson, R. Z.; Thomas, R. R., Four-dimensional polytopes of minimum positive semidefinite rank, J. Combin. Theory Ser. A, 145, 184-226, (2017) · Zbl 1360.52006
[9] Grayson, D. R.; Stillman, M. E., Macaulay2, a software system for research in algebraic geometry
[10] Mnëv, N. E., Topology and geometry — Rohlin Seminar, 1346, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, 527-543, (1988), Springer: Springer, Berlin · Zbl 0667.52006
[11] Ohsugi, H.; Hibi, T., Toric ideals generated by quadratic binomials, J. Algebra, 218, 2, 509-527, (1999) · Zbl 0943.13014
[12] Oxley, J., Matroid theory, 21, xiv+684 p. pp., (2011), Oxford University Press: Oxford University Press, Oxford · Zbl 1254.05002
[13] Rothvoss, T., STOC’14 — Proceedings of the 2014 ACM Symposium on Theory of Computing, The matching polytope has exponential extension complexity, 263-272, (2014), ACM: ACM, New York · Zbl 1315.90038
[14] Villarreal, R. H., Rees algebras of edge ideals, Comm. Algebra, 23, 9, 3513-3524, (1995) · Zbl 0836.13014
[15] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., 43, 3, 441-466, (1991) · Zbl 0748.90074
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.