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.
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.68
Keywords: matroid, realization space
Brandt, Madeline 1; Wiebe, Amy 2
@article{ALCO_2019__2_4_663_0, author = {Brandt, Madeline and Wiebe, Amy}, title = {The slack realization space of a matroid}, journal = {Algebraic Combinatorics}, pages = {663--681}, publisher = {MathOA foundation}, volume = {2}, number = {4}, year = {2019}, doi = {10.5802/alco.68}, zbl = {1420.52017}, mrnumber = {3997517}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.68/} }
TY - JOUR AU - Brandt, Madeline AU - Wiebe, Amy TI - The slack realization space of a matroid JO - Algebraic Combinatorics PY - 2019 SP - 663 EP - 681 VL - 2 IS - 4 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.68/ DO - 10.5802/alco.68 LA - en ID - ALCO_2019__2_4_663_0 ER -
Brandt, Madeline; Wiebe, Amy. The slack realization space of a matroid. Algebraic Combinatorics, Volume 2 (2019) no. 4, pp. 663-681. doi : 10.5802/alco.68. https://alco.centre-mersenne.org/articles/10.5802/alco.68/
[1] Oriented Matroids, Cambridge University Press, 1993 | Zbl
[2] Computational synthetic geometry, Lecture Notes in Mathematics, 1355, Springer-Verlag, Berlin, 1989, vi+168 pages | MR | Zbl
[3] Matroids: A Macaulay2 package (2015) (https://arxiv.org/abs/1511.04618) | Zbl
[4] Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, Undergraduate Texts in Mathematics, Springer, Cham, 2015, xvi+646 pages | Zbl
[5] Matroids: a geometric introduction, Cambridge University Press, Cambridge, 2012, xvi+393 pages | DOI | Zbl
[6] The Slack Realization Space of a Polytope (https://arxiv.org/abs/1708.04739) | Zbl
[7] Lifts of convex sets and cone factorizations, Math. Oper. Res., Volume 38 (2013) no. 2, pp. 248-264 | DOI | MR | Zbl
[8] Four-dimensional polytopes of minimum positive semidefinite rank, J. Combin. Theory Ser. A, Volume 145 (2017), pp. 184-226 | DOI | MR | Zbl
[9] Macaulay2, a software system for research in algebraic geometry (Available at http://www.math.uiuc.edu/Macaulay2/)
[10] The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, Topology and geometry — Rohlin Seminar (Lecture Notes in Math.), Volume 1346, Springer, Berlin, 1988, pp. 527-543 | DOI | MR | Zbl
[11] Toric ideals generated by quadratic binomials, J. Algebra, Volume 218 (1999) no. 2, pp. 509-527 | DOI | MR | Zbl
[12] Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, Oxford, 2011, xiv+684 pages | MR | Zbl
[13] The matching polytope has exponential extension complexity, STOC’14 — Proceedings of the 2014 ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 263-272 | Zbl
[14] Rees algebras of edge ideals, Comm. Algebra, Volume 23 (1995) no. 9, pp. 3513-3524 | DOI | MR | Zbl
[15] Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., Volume 43 (1991) no. 3, pp. 441-466 | DOI | MR | Zbl
Cited by Sources: