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 affine reducibility of combinatorial polytopes

Doklady Mathematics -     

On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

On combinatorial and affine automorphisms of polytopes

We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope in euclidean spaceE ^d can be realised by an affine transformation ofE ^d .     

Maximum semidefinite and linear extension complexity of families of polytopes

Mathematical Programming - We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance...     

On the combinatorial lower bound for the extension complexity of the Spanning Tree polytope

This paper concerns the extension complexity of the Minimum Spanning Tree problem on a complete graph with  $n$ nodes. The best known lower bound is the trivial bound, $\Omega \left(n^2\right)$, the best known upper bound is the extended formulation size $O\left(n^3\right)$ (Wong 1980, Martin 1991). We give a nondeterministic communication protocol with cost ${log}_2(n^{2}logn)+O\left(1\right)$ for the support of the spanning tree slack matrix.     

Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes

The hyperplane separation bound is a lower bound on the extension complexity of a polytope. It is the main tool in Rothvoß's proof of an exponential bound for the matching polytope (Rothvoß, 2017). We show that the technique is sensitive to the choice of slack matrix and does not improve upon the best known lower bounds for spanning tree and completion time polytopes when applied to their canonical slack matrices. Stronger bounds may be obtained by appropriate rescalings and redundancy.     

On a combinatorial problem concerning subpolytopes of stack polytopes

Shephard [6] posed the problem of whether every combinatorial type of d-polytope can be represented by some subpolytope of some d-stack. Here we show that, at least in the case d=3, the answer to that problem is in the affirmative.I am indebted to Professor G.C. Shephard for reading a preliminary version of this note and making suggestions for its improvement.     

A combinatorial generalization of polytopes

Primoids and duoids are collections of subsets of a fixed finite set with a natural generalization of a pivoting property of convex polytopes. This structure is precisely what is necessary for the application of complementary pivoting algorithms. This paper investigates the combinatorial structure of primoids and duoids, showing them to form the circuits and cocircuits of a binary matroid. This matroid is then compared with the simplicial geometries of Crapo and Rota.     

The combinatorial structure of random polytopes

Choose n random points in , let P_n be their convex hull, and denote by f_i(P_n) the number of i-dimensional faces of P_n. A general method for computing the expectation of f_i(P_n), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for f_i(P_n) is proved as n→∞. For random points chosen in a polytope the expectation of f_i(P_n) is determined as n→∞. This implies an extremal property for random points chosen in a simplex.     

On an extension of a combinatorial identity

Using Frobenius partitions we extend the main results of [4]. This leads to an infinite family of 4-way combinatorial identities. In some particular cases we get even 5-way combinatorial identities which give us four new combinatorial versions of Göllnitz-Gordon identities.     

Hirsch polytopes with exponentially long combinatorial segments

In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340–1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound \(O(n2^d)\) for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound \(n-d+1\) if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use these definitions to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length \(\Omega (n2^{d})\). This includes vertex-decomposable—therefore Hirsch—polytopes.     

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

Approximation problems for combinatorial isomorphism classes of convex polytopes

Geometriae Dedicata -     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001