On rank-perfect subclasses of near-bipartite graphs

Shepherd95 proved that the stable set polytopes of near-bipartite graphs are given by constraints associated with the complete join of antiwebs only. For antiwebs, the facet set reduces to rank constraints associated with single antiwebs by Wagler2004. We extend this result to a larger graph class, the complements of fuzzy circular interval graphs, recently introduced in ChudnovskySeymour2004. Received: November 2004 / Revised version: June 2005     

A lower bound on the Chvátal-rank of Antiwebs

In [Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of linear relaxations of the stable set polytope, International Transactions in Operational Research 17 (2010), pp. 827–849; Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of Antiwebs, Electronic Notes in Discrete Mathematics 36 (2010), pp. 183–190] we study the Chvátal-rank of the edge constraint and the clique constraint stable set polytopes related to antiwebs. We present schemes for obtaining both upper and lower bounds. Moreover, we provide an algorithm to compute the exact values of the Chvátal-rank for all antiwebs with up to 5,000 nodes. Here we prove a lower bound as a closed formula and discuss some cases when this bound is tight.     

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.      

On the set covering polyhedron of circulant matrices

A well known family of minimally nonideal matrices is the family of the incidence matrices of chordless odd cycles. A natural generalization of these matrices is given by the family of circulant matrices. Ideal and minimally nonideal circulant matrices have been completely identified by Cornuéjols and Novick [G. Cornuéjols, B. Novick, Ideal 0 - 1 matrices, Journal of Combinatorial Theory B 60 (1994) 145–157]. In this work we classify circulant matrices and their blockers in terms of the inequalities involved in their set covering polyhedra. We exploit the results due to Cornuéjols and Novick in the above-cited reference for describing the set covering polyhedron of blockers of circulant matrices. Finally, we point out that the results found on circulant matrices and their blockers present a remarkable analogy with a similar analysis of webs and antiwebs due to Pêcher and Wagler [A. Pêcher, A. Wagler, A construction for non-rank facets of stable set polytopes of webs, European Journal of Combinatorics 27 (2006) 1172–1185; A. Pêcher, A. Wagler, Almost all webs are not rank-perfect, Mathematical Programming Series B 105 (2006) 311–328] and Wagler [A. Wagler, Relaxing perfectness: Which graphs are ‘Almost’ perfect?, in: M. Groetschel (Ed.), The Sharpest Cut, Impact of Manfred Padberg and his work, in: SIAM/MPS Series on Optimization, vol. 4, Philadelphia, 2004; A. Wagler, Antiwebs are rank-perfect, 4OR 2 (2004) 149–152].     

On the maximum feasible subsystem problem,IISs and IIS-hypergraphs

 We consider the Max FS problem: For a given infeasible linear system A x≤b, determine a feasible subsystem containing as many inequalities as possible. This problem, which is NP-hard and also difficult to approximate, has a number of interesting applications in a wide range of fields. In this paper we examine structural and algorithmic properties of Max FS and of Irreducible Infeasible Subsystems (IISs), which are intrinsically related since one must delete at least one constraint from each IIS to attain feasibility. First we provide a new simplex decomposition characterization of IISs and prove that finding a smallest cardinality IIS is very difficult to approximate. Then we discuss structural properties of IIS-hypergraphs, i.e., hypergraphs in which each edge corresponds to an IIS, and show that recognizing IIS-hypergraphs subsumes the Steinitz problem for polytopes and hence is NP-hard. Finally we investigate rank facets of the Feasible Subsystem polytope whose vertices are incidence vectors of feasible subsystems of a given infeasible system. In particular, using the IIS-hypergraph structural result, we show that only two very specific types of rank inequalities induced by generalized antiwebs (which generalize cliques, odd holes and antiholes to general independence systems) can arise as facets. Received: December 2000 / Accepted: November 2002 Published online: February 14, 2003 RID="⋆" ID="⋆" Part of this work was done while the first two authors were with the School of OR&IE, Cornell University, USA. A preliminary version appeared in the Proceedings of the 10th IPCO conference [7], held in Graz, Austria, June 1999. This work was supported by NSF grant DMS-9527124. Key words. infeasible linear systems – feasible subsystems – Irreducible Infeasible Subsystem (IIS) – IIS-hypergraphs – independence systems – feasible subsystem polytope – rank facets     

The element number of the convex regular polytopes

Let Σ be a set of n-dimensional polytopes. A set Ω of n-dimensional polytopes is said to be an element set for Σ if each polytope in Σ is the union of a finite number of polytopes in Ω identified along (n − 1)-dimensional faces. In this paper, we consider the n-dimensional polytopes in general, and extend the notion of element sets to higher dimensions. In particular, we will show that in the 4-space, the element number of the six convex regular polychora is at least 2, and in the n-space (n ≥ 5), the element number is 3, unless n + 1 is a square number.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

On the polyhedral lift-and-project methods and the fractional stable set polytope

We study two polyhedral lift-and-project operators (originally proposed by Lovász and Schrijver in 1991) applied to the fractional stable set polytopes. First, we provide characterizations of all valid inequalities generated by these operators. Then, we present some seven-node graphs on which the operator enforcing the symmetry of the matrix variable is strictly stronger on the odd-cycle polytope of these graphs than the operator without this symmetry requirement. This disproves a conjecture of Lipták and Tunçel from 2003.     

Quotients of Some Finite Universal Locally Projective Polytopes

   Abstract. This paper classifies the quotients of a finite and locally projective polytope of type {4,3,5} . Seventy quotients are found, including three regular polytopes, and nine other section regular polytopes which are themselves locally projective. The classification is done with the assistance of GAP, a computer system for algebraic computation. The same techniques are also applied to two finite locally projective polytopes respectively of type {3,5,3} and {5,3,5} . No nontrivial quotients of the latter are found.     

Prodsimplicial-Neighborly Polytopes

Simultaneously generalizing both neighborly and neighborly cubical polytopes, we introduce PSN polytopes: their k-skeleton is combinatorially equivalent to that of a product of r simplices.     

Smooth Fano Polytopes Whose Ehrhart Polynomial Has a Root with Large Real Part

The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this paper, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.     

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.     

On hyperbolic virtual polytopes and hyperbolic fans

Hyperbolic virtual polytopes arose originally as polytopal versions of counterexamples to the following A.D.Alexandrov’s uniqueness conjecture: Let K ⊂ ℝ³ be a smooth convex body. If for a constant C, at every point of ∂K, we have R ₁ ≤ C ≤ R ₂ then K is a ball. (R ₁ and R ₂ stand for the principal curvature radii of ∂K.) This paper gives a new (in comparison with the previous construction by Y.Martinez-Maure and by G.Panina) series of counterexamples to the conjecture. In particular, a hyperbolic virtual polytope (and therefore, a hyperbolic hérisson) with odd an number of horns is constructed. Moreover, various properties of hyperbolic virtual polytopes and their fans are discussed.     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

Locally toroidal polytopes and modular linear groups

When the standard representation of a crystallographic Coxeter group G (with string diagram) is reduced modulo the integer d≥2, one obtains a finite group G^d which is often the automorphism group of an abstract regular polytope. Building on earlier work in the case that d is an odd prime, here we develop methods to handle composite moduli and completely describe the corresponding modular polytopes when G is of spherical or Euclidean type. Using a modular variant of the quotient criterion, we then describe the locally toroidal polytopes provided by our construction, most of which are new.