Subdivisions of integral base polytopes
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\). \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. An 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.
- Valuations for Matroid Polytope Subdivisions
- Minimization of an M-convex function
- Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2
- Matroid base polytope decomposition II: Sequences of hyperplane splits
- Polyhedra with the integer Carathéodory property
- scientific article; zbMATH DE number 3906513
- A characterization of matroidal systems of inequalities
- A characterization of uniform matroids
- Generalized polymatroids and submodular flows
- Improved bound for the Carathéodory rank of the bases of a matroid
This page was built for publication: Subdivisions of integral base polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954241)
