Changes
{{IncludeOpenProblem|Are t-perfect graphs 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 <ref>T. Király, J. Pap, ''Total dual integrality of Rothblum's description of the stable-marriage polyhedron'', [http:name="KiPa"//dx.doi.org/10.1287/moor.1070.0286 DOI link], [http://www.cs.elte.hu/egres/tr/egres-05-01.pdf EGRES Technical Report].</ref>. It may be interesting to extend this result to [[polyhedral description of kernels]] in other graph classes.
==Integer decomposition==
* polymatroids ,
* intersection of two [[base orderable matroid|base orderable matroids]],
* polyhedra defined by nearly TU matrices (Gijswijt <ref>D. Gijswijt, ''Integer decomposition for polyhedra defined by nearly totally Unimodular matrices'', [http:name="Gi"//dx.doi.org/10.1137/S089548010343569X DOI link].</ref>),* projections of polyhedra defined by TU matrices (Sebő <ref>A. Sebő, ''Path Partitions, Cycle Covers and Integer Decomposition'', [http:name="Se"//dx.doi.org/10.1007/978-3-642-02029-2_18 DOI link].</ref>),* certain polyhedra defined by ''k''-balanced matrices (Zambelli <ref>G. Zambelli, ''Colorings of k-balanced matrices and integer decomposition property of related polyhedra'', [http:name="Za"//dx.doi.org/10.1016/j.orl.2006.06.006 DOI link], [http://www.math.unipd.it/~giacomo/papers/matrix-col.pdf Author link].</ref>).
An interesting open case is the polyhedron of ''k''-arborescences, which is the intersection of two matroids, see [[Capacitated packing of k-arborescences]].
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:
{{IncludeOpenProblem|Expressing vectors using bases of a matroid}}
This [[Expressing vectors using bases of a matroid|question was recently answered]], using a very elegant proof, by Dion Gijswijt and Guus Regts <ref name="GiReGiRe2">D. Gijswijt, G. Regts, ''On the Caratheodory rank of polymatroid bases'', March 2010, [http://arxiv.org/abs/1003.1079v1 arXiv link].</ref>.
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]]:
==References==
<references>
<referencesref name="KiPa">T. Király, J. Pap, ''Total dual integrality of Rothblum's description of the stable-marriage polyhedron'', [http://dx.doi.org/10.1287/moor.1070.0286 DOI link], [http://www.cs.elte.hu/egres/tr/egres-05-01.pdf EGRES Technical Report].</ref> <ref name="Gi">D. Gijswijt, ''Integer decomposition for polyhedra defined by nearly totally Unimodular matrices'', [http://dx.doi.org/10.1137/S089548010343569X DOI link].</ref> <ref name="Se">A. Sebő, ''Path Partitions, Cycle Covers and Integer Decomposition'', [http://dx.doi.org/10.1007/978-3-642-02029-2_18 DOI link].</ref> <ref name="Za">G. Zambelli, ''Colorings of k-balanced matrices and integer decomposition property of related polyhedra'', [http://dx.doi.org/10.1016/j.orl.2006.06.006 DOI link], [http://www.math.unipd.it/~giacomo/papers/matrix-col.pdf author link].</ref> <ref name="GiRe2">D. Gijswijt, G. Regts, ''Polyhedra with the Integer Caratheodory Property'', Journal of Combinatorial Theory Series B 102 (2012), 62–70, [http://dx.doi.org/10.1016/j.jctb.2011.04.004 DOI link], [http://arxiv.org/abs/1004.4552 arXiv link].</ref> </references>
[[Category:Surveys]]
