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] Oriented Matroids, Cambridge University Press, 1993 | Zbl 0773.52001

[2] Computational synthetic geometry, Lecture Notes in Mathematics, Volume 1355, Springer-Verlag, Berlin, 1989, vi+168 pages | MR 1009366 | Zbl 0683.05015

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

[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 1335.13001

[5] Matroids: a geometric introduction, Cambridge University Press, Cambridge, 2012, xvi+393 pages | Article | Zbl 1253.05002

[6] The Slack Realization Space of a Polytope (https://arxiv.org/abs/1708.04739 ) | Zbl 1423.52032

[7] 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] 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] 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 | Article | MR 970093 | Zbl 0667.52006

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

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

[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 1315.90038

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

[15] 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