The slack realization space of a matroid
Algebraic Combinatorics, Volume 2 (2019) no. 4, p. 663-681

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.

Received : 2018-05-02
Revised : 2019-01-22
Accepted : 2019-02-23
Published online : 2019-08-01
DOI : https://doi.org/10.5802/alco.68
Classification:  52B40
Keywords: matroid, realization space
@article{ALCO_2019__2_4_663_0,
     author = {Brandt, Madeline and Wiebe, Amy},
     title = {The slack realization space of a matroid},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {4},
     year = {2019},
     pages = {663-681},
     doi = {10.5802/alco.68},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_4_663_0}
}
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/item/ALCO_2019__2_4_663_0/

[1] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. Oriented Matroids, Cambridge University Press (1993) | Zbl 0773.52001

[2] Bokowski, J.; Sturmfels, B. Computational synthetic geometry, Springer-Verlag, Berlin, Lecture Notes in Mathematics, Volume 1355 (1989), vi+168 pages | MR 1009366 | Zbl 0683.05015

[3] Chen, J. Matroids: A Macaulay2 package (2015) (https://arxiv.org/abs/1511.04618 )

[4] Cox, D. A.; Little, J.; O’Shea, D. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, Springer, Cham, Undergraduate Texts in Mathematics (2015), xvi+646 pages | Zbl 1335.13001

[5] Gordon, G.; Mcnulty, J. Matroids: a geometric introduction, Cambridge University Press, Cambridge (2012), xvi+393 pages | Article | Zbl 1253.05002

[6] Gouveia, J.; Macchia, A.; Thomas, R. R.; Wiebe, A. The Slack Realization Space of a Polytope (https://arxiv.org/abs/1708.04739 )

[7] Gouveia, J.; Parrilo, P. A.; Thomas, R. R. Lifts of convex sets and cone factorizations, Math. Oper. Res., Volume 38 (2013) no. 2, pp. 248-264 | Article | MR 3062007 | 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, Volume 145 (2017), pp. 184-226 | Article | MR 3551651 | Zbl 1360.52006

[9] Grayson, D. R.; Stillman, M. E. Macaulay2, a software system for research in algebraic geometry (Available at http://www.math.uiuc.edu/Macaulay2/)

[10] Mnëv, N. E. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, Topology and geometry — Rohlin Seminar, Springer, Berlin (Lecture Notes in Math.) Volume 1346 (1988), pp. 527-543 | Article | MR 970093 | Zbl 0667.52006

[11] Ohsugi, H.; Hibi, T. Toric ideals generated by quadratic binomials, J. Algebra, Volume 218 (1999) no. 2, pp. 509-527 | Article | MR 1705794 | Zbl 0943.13014

[12] Oxley, J. Matroid theory, Oxford University Press, Oxford, Oxford Graduate Texts in Mathematics, Volume 21 (2011), xiv+684 pages | MR 2849819 | Zbl 1254.05002

[13] Rothvoss, T. 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 1315.90038

[14] Villarreal, R. H. Rees algebras of edge ideals, Comm. Algebra, Volume 23 (1995) no. 9, pp. 3513-3524 | Article | MR 1335312 | Zbl 0836.13014

[15] Yannakakis, M. Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., Volume 43 (1991) no. 3, pp. 441-466 | Article | MR 1135472 (93a:90054) | Zbl 0748.90074