Polyhedra with the Integer Caratheodory Property

2010/04/26 by Dion Gijswijt, Gijswijt, Dion, Guus Regts +1 · 1 citation
Mathematics · #90C10 (52B40) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:90C10

paper · pdf · doi:10.48550/arxiv.1004.4552

12 pages

arxiv created 2010/04/26 · arxiv updated 2010/04/27

Abstract

A polyhedron P has the Integer Caratheodory Property if the following holds. For any positive integer k and any integer vector w in kP, there exist affinely independent integer vectors x₁,...,x_t in P and positive integers n₁,...,n_t such that n₁+...+n_t=k and w=n₁x₁+...+n_tx_t. In this paper we prove that if P is a (poly)matroid base polytope or if P is defined by a TU matrix, then P and projections of P satisfy the integer Caratheodory property.

Cited by

• Prefix-bounded matrices

Related

• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• A parameterized linear formulation of the integer hull
• Principally Box-integer Polyhedra and Equimodular Matrices
• On algebraic properties of matroid polytopes
• Enumerating projections of integer points in unbounded polyhedra