Discrete Polymatroids
Jürgen Herzog
and Takayuki Hibi
DOI: 10.1023/A:1021852421716
Abstract
The discrete polymatroid is a multiset analogue of the matroid. Based on the polyhedral theory on integral polymatroids developed in late 1960's and in early 1970's, in the present paper the combinatorics and algebra on discrete polymatroids will be studied.
Pages: 239–268
Full Text: PDF
References
1. W. Bruns and J. Herzog, Cohen-Macaulay Rings, rev. edn., Cambridge University Press, Cambridge, 1996.
2. A. Conca and J. Herzog, “Castelnuovo-Mumford regularity of products of ideals,” preprint 2001.
3. E. De Negri, “Toric rings generated by special stable sets of monomials,” Math. Nachr. 203 (1999), 31-45.
4. E. De Negri and T. Hibi, “Gorenstein algebras of Veronese type,” J. Algebra 193 (1997), 629-639.
5. J. Edmonds, “Submodular functions, matroids, and certain polyhedra,” in Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schonheim (Eds.), Gordon and Breach, New York, 1970, pp. 69-87.
6. S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Math, Vol. 47, North-Holland, Amsterdam, 1991.
7. I.M. Gelfand, R.M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial geometry, convex polyhedra, and Schubert cells,” Advances in Math. 63 (1987), 301-316.
8. J. Herzog and Y. Takayama, “Resolutions by mapping cones,” The Roos Festschrift Vol.
2. Homology Homotopy Appl. 4 (2002), 277-294.
9. T. Hibi, Algebraic Combinatorics on Convex Polytopes, Carslaw, Glebe, N.S.W., Australia, 1992.
10. K. Murota, “Convexity and Steinitz's exchange property,” Advances in Math. 124 (1996), 272-311.
11. K. Murota, “Discrete convex analysis,” Mathematical Programming 83 (1998), 313-371.
12. K. Murota, “Discrete Convex Analysis,” to appear.
13. K. Murota and A. Shioura, “M-convex function on generalized polymatroid,” Mathematics of Operations Research 24 (1999), 95-105.
14. H. Ohsugi, J. Herzog, and T. Hibi, “Combinatorial pure subrings,” Osaka J. Math. 37 (2000), 745-757.
15. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, New York, 1992.
16. B. Sturmfels, Gr\ddot obner Bases and Convex Polytopes, Amer. Math. Soc., Providence, RI, 1995.
17. D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
18. N. White, “A unique exchange property for bases,” Linear Algebra Appl. 31 (1980), 81-91.
2. A. Conca and J. Herzog, “Castelnuovo-Mumford regularity of products of ideals,” preprint 2001.
3. E. De Negri, “Toric rings generated by special stable sets of monomials,” Math. Nachr. 203 (1999), 31-45.
4. E. De Negri and T. Hibi, “Gorenstein algebras of Veronese type,” J. Algebra 193 (1997), 629-639.
5. J. Edmonds, “Submodular functions, matroids, and certain polyhedra,” in Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schonheim (Eds.), Gordon and Breach, New York, 1970, pp. 69-87.
6. S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Math, Vol. 47, North-Holland, Amsterdam, 1991.
7. I.M. Gelfand, R.M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial geometry, convex polyhedra, and Schubert cells,” Advances in Math. 63 (1987), 301-316.
8. J. Herzog and Y. Takayama, “Resolutions by mapping cones,” The Roos Festschrift Vol.
2. Homology Homotopy Appl. 4 (2002), 277-294.
9. T. Hibi, Algebraic Combinatorics on Convex Polytopes, Carslaw, Glebe, N.S.W., Australia, 1992.
10. K. Murota, “Convexity and Steinitz's exchange property,” Advances in Math. 124 (1996), 272-311.
11. K. Murota, “Discrete convex analysis,” Mathematical Programming 83 (1998), 313-371.
12. K. Murota, “Discrete Convex Analysis,” to appear.
13. K. Murota and A. Shioura, “M-convex function on generalized polymatroid,” Mathematics of Operations Research 24 (1999), 95-105.
14. H. Ohsugi, J. Herzog, and T. Hibi, “Combinatorial pure subrings,” Osaka J. Math. 37 (2000), 745-757.
15. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, New York, 1992.
16. B. Sturmfels, Gr\ddot obner Bases and Convex Polytopes, Amer. Math. Soc., Providence, RI, 1995.
17. D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
18. N. White, “A unique exchange property for bases,” Linear Algebra Appl. 31 (1980), 81-91.