no. 4
The slack realization space of a matroid
Brandt, Madeline1 ; Wiebe, Amy2
1 University of California, Berkley Dept. of mathematics 970 Evans Hall Berkeley CA 94720, USA
2 University of Washington Dept. of mathematics Box 354350 Seattle WA 98195, USA
Algebraic Combinatorics, Tome 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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.68
Classification : 52B40
Mots clés : matroid, realization space
Brandt, Madeline 1 ; Wiebe, Amy 2

1 University of California, Berkley Dept. of mathematics 970 Evans Hall Berkeley CA 94720, USA
2 University of Washington Dept. of mathematics Box 354350 Seattle WA 98195, USA 
@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},
     mrnumber = {3997517},
     zbl = {1420.52017},
     language = {en},
     url = {http://www.numdam.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  - http://www.numdam.org/articles/10.5802/alco.68/
DO  - 10.5802/alco.68
LA  - en
ID  - ALCO_2019__2_4_663_0
ER  - 
%0 Journal Article
%A Brandt, Madeline
%A Wiebe, Amy
%T The slack realization space of a matroid
%J Algebraic Combinatorics
%D 2019
%P 663-681
%V 2
%N 4
%I MathOA foundation
%U http://www.numdam.org/articles/10.5802/alco.68/
%R 10.5802/alco.68
%G en
%F ALCO_2019__2_4_663_0
Brandt, Madeline; Wiebe, Amy. The slack realization space of a matroid. Algebraic Combinatorics, Tome 2 (2019) no. 4, pp. 663-681. doi : 10.5802/alco.68. http://www.numdam.org/articles/10.5802/alco.68/

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

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

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

[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

[5] Gordon, G.; McNulty, J. Matroids: a geometric introduction, Cambridge University Press, Cambridge, 2012, xvi+393 pages | DOI | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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

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

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

Cité par Sources :