Polyhedra with the integer Carathéodory property

DOI10.1016/J.JCTB.2011.04.004zbMATH Open1252.52009arXiv1004.4552OpenAlexW2133236115MaRDI QIDQ765190FDOQ765190

Authors: Guus Regts, Dion Gijswijt 

Publication date: 19 March 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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_1,...,x_t in P and positive integers n_1,...,n_t such that n_1+...+n_t=k and w=n_1x_1+...+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.

Full work available at URL: https://arxiv.org/abs/1004.4552

Recommendations

• An integer analogue of Carathéodory's theorem
• Base polyhedra and the linking property
• Integer decomposition property of dilated polytopes
• Path Partitions, Cycle Covers and Integer Decomposition
• On the Integral Carathéodory Property

zbMATH Keywords

matroidtotally unimodular matrixinteger decompositionbase polytopeCarathéodory

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Title not available (Why is that?)
• Path Partitions, Cycle Covers and Integer Decomposition
• An integer analogue of Carathéodory's theorem
• A counterexample to an integer analogue of Carathéodory's theorem
• Improved bound for the Carathéodory rank of the bases of a matroid
• Title not available (Why is that?)
• Testing membership in matroid polyhedra
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• On greedy bases packing in matroids
• Coflow polyhedra
• Integral decomposition in polyhedra

Cited In (8)

• New Bounds for the Integer Carathéodory Rank
• On the toric ideals of matroids of a fixed rank
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Box-total dual integrality, box-integrality, and equimodular matrices
• A faster algorithm for packing branchings in digraphs
• An integer analogue of Carathéodory's theorem
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Subdivisions of integral base polytopes

This page was built for publication: Polyhedra with the integer Carathéodory property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765190)