Perturbation of transportation polytopes

We describe a perturbation method that can be used to reduce the problem of finding the multivariate generating function (MGF) of a non-simple polytope to computing the MGF of simple polytopes. We then construct a perturbation that works for any transportation polytope. We apply this perturbation to the family of central transportation polytopes of order $kn\times n$, and obtain formulas for the MGFs of the feasible cone of each vertex of the polytope and the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn\times n$.     

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.     

Seminormality,canonical modules,and regularity of cut polytopes

Motivated by a conjecture of Sturmfels and Sullivant we study normal cut polytopes. After a brief survey of known results for normal cut polytopes it is in particular observed that for simplicial and simple cut polytopes their cut algebras are normal and hence Cohen–Macaulay. Moreover, seminormality is considered. It is shown that the cut algebra of $K_5$ is not seminormal which implies again the known fact that it is not normal. For normal Gorenstein cut algebras and other cases of interest we determine their canonical modules. The Castelnuovo–Mumford regularity of a cut algebra is computed for various types of graphs and bounds for it are provided if normality is assumed. As an application we classify all graphs for which the cut algebra has regularity less than or equal to 4.     

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.     

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.     

Triangulations of Cayley and Tutte polytopes

Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun’s conjecture  , which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to two one-variable deformations of Cayley polytopes (which we call t$t$-Cayley   and t$t$-Gayley polytopes), and to the most general two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph.     

Lifted generalized permutahedra and composition polynomials

Generalized permutahedra are the polytopes obtained from the permutahedron by changing the edge lengths while preserving the edge directions, possibly identifying vertices along the way. We introduce a “lifting” construction for these polytopes, which turns an n  -dimensional generalized permutahedron into an (n+1)$(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff ?s multiplihedron from homotopy theory, and to the more general “nestomultiplihedra”, answering two questions of Devadoss and Forcey.     

Lifting inequalities for polytopes

We present a method of lifting linear inequalities for the flag f-vector of polytopes to higher dimensions. Known inequalities that can be lifted using this technique are the non-negativity of the toric g-vector and that the simplex minimizes the cd-index. We obtain new inequalities for six-dimensional polytopes. In the last section we present the currently best known inequalities for dimensions 5 through 8.     

Théorie des hérissons et polytopes

We show how it is possible to give a general character to the theory of hedgehogs (i.e., of geometric differences of convex bodies of $\text{R}{}^{\mathrm{n+1}}$). In particular, we show how it is possible to extend the theory to polytopes for which we study notions of weak and strong hyperbolicity in $\text{R}{}^3$. Finally, we consider the extension of the Minkowski Problem. To cite this article: Y. Martinez-Maure, C. R. Acad. Sci. Paris, Ser. I 336 (2003).