# 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