Integer decomposition property
From Egres Open
A polyhedron P has the integer decomposition property, if for any natural number k and any integer vector [math]x\in kP[/math], there exist k integer vectors [math]x_1,\ldots,x_k\in P[/math] with [math]x_1+\ldots+x_k=x[/math]. Here kP is the set of vectors which can be decomposed to the sum of k (not necessarly integer) vectors in P. Polytopes having the integer decomposition property are also called normal polytopes.
Examples
Some classes of polyhedra with integer decomposition property:
- polymatroids,
- intersection of two base orderable matroids,
- polyhedron of arborescences (see Edmonds' disjoint arborescences theorem),
- polyhedra defined by nearly TU matrices (Gijswijt [1]),
- projections of polyhedra defined by TU matrices (Sebő [2]),
- certain polyhedra defined by k-balanced matrices (Zambelli [3]),
- stable set polytope of claw-free t-perfect graphs and h-perfect line-graphs (Benchetrit [4]).
References
- ↑ D. Gijswijt, Integer decomposition for polyhedra defined by nearly totally Unimodular matrices, DOI link
- ↑ A. Sebő, Path Partitions, Cycle Covers and Integer Decomposition, DOI link, author link
- ↑ G. Zambelli, Colorings of k-balanced matrices and integer decomposition property of related polyhedra, DOI link, Author link
- ↑ Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link
