Integer decomposition property

From Egres Open
Jump to: navigation, search

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.


Some classes of polyhedra with integer decomposition property:


  1. D. Gijswijt, Integer decomposition for polyhedra defined by nearly totally Unimodular matrices, DOI link
  2. A. Sebő, Path Partitions, Cycle Covers and Integer Decomposition, DOI link, author link
  3. G. Zambelli, Colorings of k-balanced matrices and integer decomposition property of related polyhedra, DOI link, Author link
  4. Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link