Discrete polymatroids (Q1863000): Difference between revisions

The discrete polymatroid is a multiset analogue of the matroid. This paper studies the combinatorics and the algebra on discrete polymatroids. An algebraic aspect of this paper is to study Ehrhart rings and base rings together with toric ideals of discrete polymatroids. One result on toric ideals of discrete polymatroids given in this paper is Theorem. (a) Suppose that each matroid has the property that the toric ideal of its base ring is generated by symmetric exchange relations, then this is also true for each discrete polymatroid. (b) If \(P \subset \mathbb{Z}^n_+\) is a discrete polymatroid whose set of base \(B\) satisfies the strong exchange property (i.e., if \(u =(u_1,\ldots, u_n),\;v=(v_1,\ldots, v_n)\in B\), then for all \(i\) and \(j\) with \(u_i >v_i\) and \(u_j <v_j\) one has \(u-\varepsilon_i - \varepsilon_j \in B)\), then (i) \(I_B\) has a quadratic Gröbner basis, and hence \(K[B]\) is Koszul; (ii) \(I_B\) is generated by symmetric exchange relations. Since both \(K[P]\) and \(K[B]\) are Cohen-Macaulay, it is natural for the authors to compare algebraic poperties of \(K[P]\) with those of \(K[B]\). A combinatorial criterion for \(K[P]\) to be Gorenstein is given. A combinatorial characterization for discrete polymatroids \(P\) satisfying \(P\) is generic and the base ring of \(P\) is Gorenstein is also given. The authors discuss base polytopes of discrete polymatroids and prove the following Theorem. An integral convex polytope \({\mathcal Q} \subset V^{(d)}_n\) is the base polytope of a discrete polymatroid \(P \subset \mathbb{Z}^n_+\) of rank \(d\) if and only if, for any vectors \(a\) and \(b\) belonging to \(\mathbb{Z}^n_+\), the integral convex polytope \({\mathcal Q}_{a,b}\) possesses the property that if \(u\) and \(v\) are vertices of \({\mathcal Q}_{a,b}\) and if the segment \(\text{conv}\{u,v\}\) is an edge of \({\mathcal Q}_{a,b}\), then \(v-u\) is of the form \(\ell(\varepsilon_i -\varepsilon_j)\), where \(i \neq j\) and \(0\neq \ell \in \mathbb{Z}_+\). The authors conclude the paper with two simple techniques to construct discrete polymatroids.