TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities. T3 - ZIB-Report - 04-53 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8284 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope N2 - \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope. T3 - ZIB-Report - 06-38 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9328 ER -