# ALGEBRAIC COMBINATORICS

The slack realization space of a matroid
Algebraic Combinatorics, Volume 2 (2019) no. 4, pp. 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.

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},
mrnumber = {3997517},
zbl = {1420.52017},
language = {en},
url = {alco.centre-mersenne.org/item/ALCO_2019__2_4_663_0/}
}
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/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, Lecture Notes in Mathematics, Volume 1355, Springer-Verlag, Berlin, 1989, vi+168 pages | MR 1009366 | Zbl 0683.05015

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

[4] Cox, D. A.; Little, J.; O’Shea, D. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, Undergraduate Texts in Mathematics, Springer, Cham, 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 ) | Zbl 1423.52032

[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 (Lecture Notes in Math.) Volume 1346, Springer, Berlin, 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 Graduate Texts in Mathematics, Volume 21, Oxford University Press, Oxford, 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 | Zbl 0748.90074