Lovász, László; Schrijver, A. Matrix cones, projection representations, and stable set polyhedra. (English) Zbl 0745.05024 Polyhedral combinatorics, Proc. Workshop, Morristown/NJ (USA) 1989, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 1, 1-17 (1990). Summary: [For the entire collection see Zbl 0722.00003.]It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron is a powerful tool in polyhedra combinatorics. We develop a general method to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0-1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.In the special case of the vertex packing polytope, we obtain a sequence of systems of inequalities, such that already the first system includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, the first system gives the vertex packing polytope. For various classes of graphs, including \(t\)-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets. Cited in 5 Documents MSC: 05C35 Extremal problems in graph theory 90C10 Integer programming 90C27 Combinatorial optimization Keywords:matrix cones; stable set polyhedra; vertex packing polytope; stable set polytope; projection of a polytope Citations:Zbl 0722.00003 PDFBibTeX XMLCite \textit{L. Lovász} and \textit{A. Schrijver}, in: Random volumes in the \(n\)-cube. . 1--17 (1990; Zbl 0745.05024)