On the linear extension complexity of stable set polytopes for perfect graphs

We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-joins and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behavior of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs.     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

Flow polytopes and the graph of reflexive polytopes

We suggest defining the structure of an unoriented graph R_d on the set of reflexive polytopes of a fixed dimension d. The edges are induced by easy mutations of the polytopes to create the possibility of walks along connected components inside this graph. For this, we consider two types of mutations: Those provided by performing duality via nef-partitions, and those arising from varying the lattice. Then for d≤3, we identify the flow polytopes among the reflexive polytopes of each single component of the graph R_d. For this, we present for any dimension d≥2 an explicit finite list of quivers giving all d-dimensional reflexive flow polytopes up to lattice isomorphism. We deduce as an application that any such polytope has at most 6(d−1) facets.     

Gal’s conjecture for nestohedra corresponding to complete bipartite graphs

Convex polytopes have interested mathematicians since very ancient times. At present, they occupy a central place in convex geometry, combinatorics, and toric topology and demonstrate the harmony and beauty of mathematics. This paper considers the problem of describing the f-vectors of simple flag polytopes, that is, simple polytopes in which any set of pairwise intersecting facets has nonempty intersection. We show that for each nestohedron corresponding to a connected building set, the h-polynomial is a descent-generating function for some class of permutations; we also prove Gal’s conjecture on the nonnegativity of γ-vectors of flag polytopes for nestohedra constructed over complete bipartite graphs.     

Lattice-free polytopes and their diameter

A convex polytope in real Euclidean space islattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and combinatorial properties of such polytopes are studied. First, bounds on some invariants, such as the diameter and layer-number, are given. It is shown that the diameter of ad-dimensional lattice-free polytope isO(d ³). A bound ofO(nd+d ³) on the diameter of ad-polytope withn facets is deduced for a large class of integer polytopes. Second, Delaunay polytopes and [0, 1]-polytopes, which form major subclasses of lattice-free polytopes, are considered. It is shown that, up to affine equivalence, for anyd≥3 there are infinitely manyd-dimensional lattice-free polytopes but only finitely many Delaunay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytopes are discussed, and the inclusion relations among the subclasses above are examined. It is shown that the classes of combinatorial-types of Delaunay polytopes and [0,1]-polytopes are mutually incomparable starting in dimension six, and that both are strictly contained in the class of combinatorial-types of all lattice-free polytopes. This research was supported by DIMACS—the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University.