Multitriangulations, Pseudotriangulations and Primitive Sorting Networks

We study the set of all pseudoline arrangements with contact points which cover a given support. We define a natural notion of flip between these arrangements and study the graph of these flips. In particular, we provide an enumeration algorithm for arrangements with a given support, based on the properties of certain greedy pseudoline arrangements and on their connection with sorting networks. Both the running time per arrangement and the working space of our algorithm are polynomial. As the motivation for this work, we provide in this paper a new interpretation of both pseudotriangulations and multitriangulations in terms of pseudoline arrangements on specific supports. This interpretation explains their common properties and leads to a natural definition of multipseudotriangulations, which generalizes both. We study elementary properties of multipseudotriangulations and compare them to iterations of pseudotriangulations.     

Alcoved Polytopes,I

The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of these polytopes. In particular, we study a class of matroid polytopes, which we call the multi-hypersimplices.     

The graphs of polytopes with involutory automorphisms

Steinitz’ theorem states that a graph is the graph of a 3-dimensional convex polytope if and only if it is planar and 3-connected. Grünbaum has shown that Steinitz’ proof can be modified to characterize the graphs of polytopes that are centrally symmetric or have a plane of symmetry. We show how to modify Steinitz’ proof to take care of the remaining involutory case—polytopes that are symmetric about a line. Research supported by NSF Grant GP-3470.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

A note on node packing polytopes on hypergraphs

A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph.     

The graph of an abstract polytope

Recently a generalization of simple convex polytopes to combinatorial entities known as abstract polytopes has been proposed. The graph of an abstract polytope of dimensiond is a regular connected graph of degreed. Given a connected regular graph of degreed, it is interesting to find out whether it is the graph of some abstract polytopeP. We obtain necessary and sufficient conditions for this, in terms of the existence of a class of simple cycles in satisfying certain properties. The main result in this paper is that if a pair of simple convex polytopes or abstract polytopes have the same two-dimensional skeleton, then they are isomorphic. Every two-dimensional face of a simple convex polytope or an abstract polytope is a simple cycle in its graph. Given the graph of a simple convex polytope or an abstract polytope and the simple cycles in this graph corresponding to all its two-dimensional faces, then we show how to construct all its remaining faces. Given a regular connected graph and a class of simple cylesD in it, we provide necessary and sufficient conditions under whichD is the class of two-dimensional faces of some abstract polytope which has as its graph.This research has been partially supported by the ISDOS Research Project at the Department of Industrial and Operations Engineering, and by the National Science Foundation under Grant No. GK-27872 with the University of Michigan.     

Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

Polytopality and Cartesian products of graphs

We study the question of polytopality of graphs: when is a given graph the graph of a polytope? We first review the known necessary conditions for a graph to be polytopal, and we present three families of graphs which satisfy all these conditions, but which nonetheless are not graphs of polytopes. Our main contribution concerns the polytopality of Cartesian products of non-polytopal graphs. On the one hand, we show that products of simple polytopes are the only simple polytopes whose graph is a product. On the other hand, we provide a general method to construct (non-simple) polytopal products whose factors are not polytopal.     

Pseudograph associahedra

Given a simple graph G, the graph associahedron KG is a simple polytope whose face poset is based on the connected subgraphs of G. This paper defines and constructs graph associahedra in a general context, for pseudographs with loops and multiple edges, which are also allowed to be disconnected. We then consider deformations of pseudograph associahedra as their underlying graphs are altered by edge contractions and edge deletions.     

Equidecomposable and weakly neighborly polytopes

A polytope is equidecomposable if all its triangulations have the same face numbers. For an equidecomposable polytope all minimal affine dependencies have an equal number of positive and negative coefficients. A subclass consists of the weakly neighborly polytopes, those for which every set of vertices is contained in a face of at most twice the dimension as the set. Theh-vector of every triangulation of a weakly neighborly polytope equals theh-vector of the polytope itself. Combinatorial properties of this class of polytopes are studied. Gale diagrams of weakly neighborly polytopes with few vertices are characterized in the spirit of the known Gale diagram characterization of Lawrence polytopes, a special class of weakly neighborly polytopes.     

Pre-Triangulations and Liftable Complexes

We introduce the concept of pre-triangulations, a relaxation of triangulations that goes beyond the frequently used concept of pseudo-triangulations. Pre-triangulations turn out to be more natural than pseudo-triangulations in certain cases. We show that pre-triangulations arise in three different contexts: In the characterization of polygonal complexes that are liftable to three-space in a strong sense, in flip sequences for general polygonal complexes, and as graphs of maximal locally convex functions. Research supported by the FWF Joint Research Project ‘Industrial Geometry’ S9205-N12.     

Decomposing the Secondary Cayley Polytope

The vertices of the secondary polytope of a point configuration correspond to its regular triangulations. The Cayley trick links triangulations of one point configuration, called the Cayley polytope, to the fine mixed subdivisions of a tuple of point configurations. In this paper we investigate the secondary polytope of this Cayley polytope. Its vertices correspond to all regular mixed subdivisions of a tuple of point configurations. We demonstrate that it equals the Minkowski sum of polytopes, which we call mixed secondary polytopes, whose vertices correspond to regular-cell configurations. Received October 1, 1998, and in revised form July 23, 1999.     

Non-connected toric Hilbert schemes

We construct small (50 and 26 points, respectively) point sets in dimension 5 whose graphs of triangulations are not connected. These examples improve our construction in J. Amer. Math. Soc. 13:3 (2000), 611–637 not only in size, but also in that the associated toric Hilbert schemes are not connected either, a question left open in that article. Additionally, the point sets can easily be put into convex position, providing examples of 5-dimensional polytopes with non-connected graph of triangulations.Mathematics Subject Classification (2000): Primary 52B11; Secondary 52B20The main result in this paper was obtained in the fall of 2001, while I was a visiting professor in the Department of Mathematics, U.C. Davis, supported by U. C. Davis, M.S.R.I. and the Spanish Government. I am also partially supported by grant BFM2001–1153 of the Spanish Dirección General de Enseñanza Superior e Investigación Científica. The paper is dedicated to Bernd Sturmfels on his 40th birthday.     

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).     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

Addition and decomposition of convex polytopes

A new addition of convex polytopes is defined and the possibility of representing each polytope as a sum of “standard” polytopes is established The research reported in this paper was supported in part by the National Science Foundation NSF-G 19838, and by the Air Force Office of Scientific Research grant AF EOAR 63-63. Lecture delivered by the second author at a symposium on Series and Geometry in Linear Spaces, held at the Hebrew University of Jerusalem from March 16 till March 24, 1964.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.