Integer polyhedra

Problems in this category

• Are t-perfect graphs strongly t-perfect?
• Are there deletion-contraction formulas for the polymatroid Tutte polynomial?
• Characterizing integral g-polymatroids
• Conforti-Cornuéjols conjecture on the MFMC property
• Expressing vectors using bases of a matroid
• Integer decomposition of smooth polytopes
• Maximum weight bounded fractional matching
• Opposite vertices of base polyhedra
• Orientation of nonideal clutters
• Orientation-compatible w-vertex cover
• Polyhedral description of kernels

Introduction

Several fundamental results of combinatorial optimization, such as Edmonds' matching polytope theorem, or the Edmonds-Giles theorem, deal with the integrality of polyhedra. These results have been generalized in several directions, and today we have a vast knowledge of the integrality properties of polyhedra defined by various types of constraints. However, there are some really elegant conjectures that are unresolved, and which suggest that there may still be deep theoretical insights to be made.

Total dual integrality

Total dual integrality has probably been the most powerful tool to prove integrality of polyhedra arising from combinatorial problems. The reason is that very often the natural linear description of the integer polyhedron turns out to be totally dual integral. Several conjectures suggest that this is true for large classes of integer polyhedra. One of the most striking is the Conforti-Cornuéjols conjecture on the MFMC property:

Is it true that a clutter has the MFMC property if and only if it has the packing property?

A well-studied class is the system of clique inequalities of graphs: the system is TDI if and only if it defines an integer polyhedron (i.e. the graph is perfect). It is an exciting question how far this can be extended. One particular question concerns t-perfect graphs:

Is it true that every t-perfect graph is strongly t-perfect?

Total dual integrality also appears in the context of stable matchings: the linear description of the stable marriage polytope by Rothblum is TDI . It may be interesting to extend this result to polyhedral description of kernels in other graph classes.

Integer decomposition

Relatively few results are known about the integer decomposition property, although it is a natural and useful property that is also relevant to other fields, like algebraic geometry. Known classes of polyhedra with integer decomposition property include the following:

• polymatroids ,
• intersection of two base orderable matroids,
• polyhedra defined by nearly TU matrices (Gijswijt ),
• projections of polyhedra defined by TU matrices (Sebő ),
• certain polyhedra defined by k-balanced matrices (Zambelli ).

A candidate for a broad class has been suggested by Oda:

Is it true that every smooth polytope has the integer decomposition property?

Another interesting open case is the polyhedron of k-arborescences, which is the intersection of two matroids, see Capacitated packing of k-arborescences.

Small certificates of membership

Carathéodory's theorem asserts that a point in a polytope can be expressed as a convex combination of at most n+1 vertices, and this is obviously best possible. The integer analogue of this question, concerning the Carathéodory rank, is much more difficult, even for well-studied polytopes like matroids:

Let M be a matroid on a ground-set of n elements, and z a vector which is the sum of the characteristic vectors of some bases. Can z be expressed as the non-negative integer-valued linear combination of at most n bases?

This question was recently answered, using a very elegant proof, by Dion Gijswijt and Guus Regts .

It may be useful to investigate polytopes that have only one integer interior point. This is the case in the open problem on Opposite vertices of base polyhedra:

Is it true that if all vertices of a base polyhedron B are in [math]\{0,1,-1\}^n[/math] and [math]0 \in B[/math], then B has a vertex v such that -v is also a vertex?

Integer preimages

The integer decomposition property can be considered as part of a larger framework: we say that a polyhedron P and a linear transformation f have the integer preimage property if every integer point in f(P) has an integer preimage in P. The task is to find classes of polyhedron-transformation pairs which have this property. For example:

• P is a box-integer polyhedron (for example a generalized polymatroid) and f is a projection,
• The integer decomposition property is obtained by considering [math]f:{\mathbb R}^{nk}\to {\mathbb R}^n[/math] defined by [math]f(x_1,\dots,x_k)=x_1+\dots+x_k[/math].