Polyhedra with the integer Carathéodory property

DOI10.1016/J.JCTB.2011.04.004MaRDI QIDQ765190zbMATHOpenAlexFDO

Authors Guus Regts, Dion Gijswijt

Publication date 19 March 2012

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

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

zbMATH Keywords

matroidtotally unimodular matrixinteger decompositionbase polytopeCarathéodory

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(9)

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

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)