Subdivisions of integral base polytopes (Q5954241)

If \(S\) is a nonempty finite set, then an integer-valued set function \(f:2^S \to\mathbb{Z}\) is called submodular if \(f(A)+ f(B)\geq f(A\cap B)+ f(A \cup B)\) for all \(A,B\subset S\). For an integer-valued submodular function \(f\), we call \(\{p\in \mathbb{R}^S\mid \sum_{x\in A} p(x)\leq f(A)\) for all \(A\subset S\), and \(\sum_{x\in S}p(x) =f(S)\}\) the integral base polytope of \(f\).NEWLINENEWLINENEWLINE\textit{K. Murota} [Math. Program. 83A, No. 3, 313-371 (1998; Zbl 0920.90103)] showed that any polytope that is the union of a finite number of integral base polytopes is an integral base polytope. Using this and other results the author shows that an integral base polytope can be divided into two integral base polytopes if and only if there exists a hyperplane by which the section of the polytope is an integral base polytope.NEWLINENEWLINENEWLINEAn integral base polytope is said to be matroidal if it can be obtained by a translation of the integral base polytope of a matroid. The author proves that an integral base polytope that is not matroidal is two-divisible, that is, it has an integral base subdivision that has exactly two polytopes having maximal dimension. The paper closes with divisibility of uniform matroids.