Quadratic Gröbner bases for smooth 3\times 3 transportation polytopes
Christian Haase
and Andreas Paffenholz
DOI: 10.1007/s10801-009-0173-4
Abstract
The toric ideals of 3\times 3 transportation polytopes T rc \mathsf{T}_{\mathbf{rc}} are quadratically generated. The only exception is the Birkhoff polytope B 3.
If T rc \mathsf{T}_{\mathbf{rc}} is not a multiple of B 3, these ideals even have square-free quadratic initial ideals. This class contains all smooth 3\times 3 transportation polytopes.
Pages: 477–489
Keywords: keywords toric ideal; Gröbner basis; quadratic triangulation; transportation polytope
Full Text: PDF
References
1. Baldoni-Silva, W., de Loera, J., Vergne, M.: Counting integer flows in networks. Found. Comput. Math. 4(3), 277-314 (2004)
2. Beck, M., Chen, B., Fukshansky, L., Haase, C., Knutson, A., Reznick, B., Robins, S., Schürmann, A.: Problems from the cottonwood room. In: Integer Points in Polyhedra-Geometry, Number Theory, Algebra, Optimization. Contemp. Math., vol. 374, pp. 179-191. Am. Math. Soc., Providence (2005)
3. Bögvad, R.: On the homogeneous ideal of a projective nonsingular toric variety. arXiv (1995)
4. Bruns, W., Gubeladze, J., Trung, N.: Normal polytopes,triangulations and Koszul algebras. J. Reine Angew. Math. 485, 123-160 (1997)
5. Diaconis, P., Eriksson, N.: Markov bases for noncommutative Fourier analysis of ranked data. J. Symb. Comput. 41(2), 182-195 (2006)
6. Ewald, G., Schmeinck, A.: Representation of the Hirzebruch-Kleinschmidt varieties by quadrics. Beitr. Algebra Geom. 34(2), 151-156 (1991)
7. Fulton, W.: Introduction to toric varieties. In: The William H. Roever Lectures in Geometry. Annals of Mathematics Studies, vol.
131. Princeton University Press, Princeton (1993)
8. Gawrilow, E., Joswig, M.: Geometric reasoning with polymake. (2005)
9. Hellus, M., Hoa, L., Stückrad, J.: Gröbner bases for simplicial toric ideals. (2007)
10. Koelman, R.: A criterion for the ideal of a projectively embedded surface to be generated by quadrics. Beitr. Algebra Geom. 34(1), 57-62 (1993)
11. Lee, C.W.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 271-290. CRC Press, New York (1997)
12. Lenz, M.: Toric ideals of flow polytopes. Master's thesis, Freie Universität Berlin (2007). see also
13. Ohsugi, H., Hibi, T.: Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. Proc. Am. Math. Soc. 129(9), 2541-2546 (2001)
14. Piechnik, L.C.: Smooth reflexive 4-polytopes have quadratic triangulations. Undergraduate thesis, Duke University (2004)
15. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)
16. Sturmfels, B.: Equations defining toric varieties. In: Algebraic Geometry-Santa Cruz
1995. Proc. Sympos. Pure Math., vol. 62, pp. 437-449. Am. Math. Soc., Providence (1997).
17. Sturmfels, B.: Gröbner Bases and Convex Polytopes. University Lecture Series, vol.
8. Am. Math. Soc., Providence (1996)
18. Sullivant, S.: Compressed polytopes and statistical disclosure limitation. Tohôku Math. J. 58(3), 433- 445 (2006).
2. Beck, M., Chen, B., Fukshansky, L., Haase, C., Knutson, A., Reznick, B., Robins, S., Schürmann, A.: Problems from the cottonwood room. In: Integer Points in Polyhedra-Geometry, Number Theory, Algebra, Optimization. Contemp. Math., vol. 374, pp. 179-191. Am. Math. Soc., Providence (2005)
3. Bögvad, R.: On the homogeneous ideal of a projective nonsingular toric variety. arXiv (1995)
4. Bruns, W., Gubeladze, J., Trung, N.: Normal polytopes,triangulations and Koszul algebras. J. Reine Angew. Math. 485, 123-160 (1997)
5. Diaconis, P., Eriksson, N.: Markov bases for noncommutative Fourier analysis of ranked data. J. Symb. Comput. 41(2), 182-195 (2006)
6. Ewald, G., Schmeinck, A.: Representation of the Hirzebruch-Kleinschmidt varieties by quadrics. Beitr. Algebra Geom. 34(2), 151-156 (1991)
7. Fulton, W.: Introduction to toric varieties. In: The William H. Roever Lectures in Geometry. Annals of Mathematics Studies, vol.
131. Princeton University Press, Princeton (1993)
8. Gawrilow, E., Joswig, M.: Geometric reasoning with polymake. (2005)
9. Hellus, M., Hoa, L., Stückrad, J.: Gröbner bases for simplicial toric ideals. (2007)
10. Koelman, R.: A criterion for the ideal of a projectively embedded surface to be generated by quadrics. Beitr. Algebra Geom. 34(1), 57-62 (1993)
11. Lee, C.W.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 271-290. CRC Press, New York (1997)
12. Lenz, M.: Toric ideals of flow polytopes. Master's thesis, Freie Universität Berlin (2007). see also
13. Ohsugi, H., Hibi, T.: Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. Proc. Am. Math. Soc. 129(9), 2541-2546 (2001)
14. Piechnik, L.C.: Smooth reflexive 4-polytopes have quadratic triangulations. Undergraduate thesis, Duke University (2004)
15. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)
16. Sturmfels, B.: Equations defining toric varieties. In: Algebraic Geometry-Santa Cruz
1995. Proc. Sympos. Pure Math., vol. 62, pp. 437-449. Am. Math. Soc., Providence (1997).
17. Sturmfels, B.: Gröbner Bases and Convex Polytopes. University Lecture Series, vol.
8. Am. Math. Soc., Providence (1996)
18. Sullivant, S.: Compressed polytopes and statistical disclosure limitation. Tohôku Math. J. 58(3), 433- 445 (2006).
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition