Extended formulations for radial cones

This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.     

On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.     

A note on the disjunctive index of joined a-perfect graphs

In this paper we present a lower bound of the disjunctive rank of the facets describing the stable set polytope of joined a-perfect graphs. This class contains near-bipartite, t-perfect, h-perfect and complement of fuzzy interval graphs, among others. The stable set polytope of joined a-perfect graphs is described by means of full rank constraints of its node induced prime antiwebs. As a first step, we completely determine the disjunctive rank of all these constraints. Using this result we obtain a lower bound of the disjunctive index of joined a-perfect graphs and prove that this bound can be achieved. In addition, we completely determine the disjunctive index of every antiweb and observe that it does not always coincide with the disjunctive rank of its full rank constraint.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Leading coefficients of Morris type constant term identities

The Morris constant term identity is known to be equivalent to the famous Selberg integral. In this paper, we regard Morris type constant terms as polynomials of a certain parameter. Thus, we can take the leading coefficients and obtain new identities. These identities happen to be crucial in finding lower bounds for cardinalities of some restricted sumsets, and in calculating the volume of a Tesler polytope.     

Characterizing and bounding the imperfection ratio for some classes of graphs

Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) equals the fractional stable set polytope QSTAB(G). The dilation ratio of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs G such that all facets of STAB(G) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively.      

The number of extreme points of tropical polyhedra

The celebrated upper bound theorem of McMullen determines the maximal number of extreme points of a polyhedron in terms of its dimension and the number of constraints which define it, showing that the maximum is attained by the polar of the cyclic polytope. We show that the same bound is valid in the tropical setting, up to a trivial modification. Then, we study the tropical analogues of the polars of a family of cyclic polytopes equipped with a sign pattern. We construct bijections between the extreme points of these polars and lattice paths depending on the sign pattern, from which we deduce explicit bounds for the number of extreme points, showing in particular that the upper bound is asymptotically tight as the dimension tends to infinity, keeping the number of constraints fixed. When transposed to the classical case, the previous constructions yield some lattice path generalizations of Gale's evenness criterion.     

Forest covers and a polyhedral intersection theorem

Aforest cover of a graph is a spanning forest for which each component has at least two nodes. We consider the convex hull of incidence vectors of forest covers in a graph and show that this polyhedron is the intersection of the forest polytope and the cover polytope. This polytope has both the spanning tree and perfect matching polytopes as faces. Further, the forest cover polytope remains integral with the addition of the constraint requiring that, for some integerk, exactlyk edges be used in the solution.Research done while thae authors were visiting the Institut für Ökonometrie und Operations Research, Universität Bonn, West Germany.Financial support provided by the Natural Sciences and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeneinschaft, SFB 303).     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

Lower bounds for real solutions to sparse polynomial systems

We show how to construct sparse polynomial systems that have non-trivial lower bounds on their numbers of real solutions. These are unmixed systems associated to certain polytopes. For the order polytope of a poset P this lower bound is the sign-imbalance of P and it holds if all maximal chains of P have length of the same parity. This theory also gives lower bounds in the real Schubert calculus through the sagbi degeneration of the Grassmannian to a toric variety, and thus recovers a result of Eremenko and Gabrielov.     

Facets and volume of Gorenstein Fano polytopes

It is known that every integral convex polytope is unimodularly equivalent to a face of some Gorenstein Fano polytope. It is then reasonable to ask whether every normal polytope is unimodularly equivalent to a face of some normal Gorenstein Fano polytope. In the present paper, it is shown that, by giving new classes of normal Gorenstein Fano polytopes, each order polytope as well as each chain polytope of dimension d is unimodularly equivalent to a facet of some normal Gorenstein Fano polytopes of dimension . Furthermore, investigation on combinatorial properties, especially, Ehrhart polynomials and volume of these new polytopes will be achieved. Finally, some curious examples of Gorenstein Fano polytopes will be discovered.     

A Brunn-Minkowski inequality for the integer lattice

A close discrete analog of the classical Brunn-Minkowksi inequality that holds for finite subsets of the integer lattice is obtained. This is applied to obtain strong new lower bounds for the cardinality of the sum of two finite sets, one of which has full dimension, and, in fact, a method for computing the exact lower bound in this situation, given the dimension of the lattice and the cardinalities of the two sets. These bounds in turn imply corresponding new bounds for the lattice point enumerator of the Minkowski sum of two convex lattice polytopes. A Rogers-Shephard type inequality for the lattice point enumerator in the plane is also proved.

     

On locally spherical polytopes of type {5, 3, 5}

There are only finitely many locally projective regular polytopes of type {5, 3, 5}. They are covered by a locally spherical polytope whose automorphism group is J₁×J₁×L₂(19), where J₁ is the first Janko group, of order 175560, and L₂(19) is the projective special linear group of order 3420. This polytope is minimal, in the sense that any other polytope that covers all locally projective polytopes of type {5, 3, 5} must in turn cover this one.     

A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

Combinatorics of Polytopes with a Group of Linear Symmetries of Prime Power Order

Generalizing a result of Stanley on centrally symmetric polytopes, Adin has derived tight lower bounds for the face numbers of a rational simplical polytope equipped with a fixed-point-free linear action of a cyclic group G of prime power order. The main goal of this paper is to extend these results further by replacing Adins fixed-point-free condition with the assumption that the action of G is proper. As corollaries, we obtain a generalization of Adins equivariant lower bound theorem and of a condition by Stanley implying combinatorial isomorphism with a minimal polytope. Finally, we prove sufficiency of an equivariant version of the McMullen and Walkup generalized lower bound conjecture.     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

Extended formulations for matroid polytopes through randomized protocols

The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.