On the Vertices of the d-Dimensional Birkhoff Polytope

Let us denote by Ω _n the Birkhoff polytope of n×n doubly stochastic matrices. As the Birkhoff–von Neumann theorem famously states, the vertex set of Ω _n coincides with the set of all n×n permutation matrices. Here we consider a higher-dimensional analog of this basic fact. Let $\varOmega^{(2)}_{n}$ be the polytope which consists of all tristochastic arrays of order n. These are n×n×n arrays with nonnegative entries in which every line sums to 1. What can be said about $\varOmega ^{(2)}_{n}$ ’s vertex set? It is well known that an order-n Latin square may be viewed as a tristochastic array where every line contains n?1 zeros and a single 1 entry. Indeed, every Latin square of order n is a vertex of $\varOmega^{(2)}_{n}$ , but as we show, such vertices constitute only a vanishingly small subset of $\varOmega^{(2)}_{n}$ ’s vertex set. More concretely, we show that the number of vertices of $\varOmega ^{(2)}_{n}$ is at least $(L_{n})^{\frac{3}{2}-o(1)}$ , where L _n is the number of order-n Latin squares. We also briefly consider similar problems concerning the polytope of n×n×n arrays where the entries in every coordinate hyperplane sum to 1, improving a result from Kravtsov (Cybern. Syst. Anal., 43(1):25–33, 2007). Several open questions are presented as well.     

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.     

Facets of the Graph Coloring Polytope

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.     

Critical Facets of the Stable Set Polytope

Dedicated to the memory of Paul Erdős A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an -critical graph. We extend several results from the theory of -critical graphs to facets. The defect of a nontrivial, full-dimensional facet of the stable set polytope of a graph G is defined by . We prove the upper bound for the degree of any node u in a critical facet-graph, and show that can occur only when . We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewell [11]. As an application of these techniques we sharpen a result of Surányi [13] by showing that if an -critical graph has defect and contains nodes of degree , then the graph is an odd subdivision of . Received October 23, 1998     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

The Contact Polytope of the Leech Lattice

The contact polytope of a lattice is the convex hull of its shortest vectors. In this paper we classify the facets of the contact polytope of the Leech lattice up to symmetry. There are 1,197,362,269,604,214,277,200 many facets in 232 orbits.     

A Linear Bound On The Diameter Of The Transportation Polytope*

We prove that the combinatorial diameter of the skeleton of the polytope of feasible solutions of any m×n transportation problem is at most 8(m+n−2). * Research for this paper was done while the second and third author were visiting the Isaac Newton Institute for Mathematical Sciences, Cambridge, U.K. All authors were supported by the TMR Network DONET of the European Community ERB TMRXCT98-0202. † Research partially funded by the Dutch BSIK/BRICKS project.     

匹配多面体的一个性质

证明了若M（G）为图G的匹配多面体,M1,M2为M（G）的两个距离为d的顶点,则M1,M2间有d条内部不相交的最短路．     

A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

Delaunay Transformations of a Delaunay Polytope

Let P be a Delaunay polytope in ⁿ . Let T(P) denote the set of affine bijections f of ⁿ for which f (P) is again a Delaunay polytope. The relation: fg if f, g differ by an orthogonal transformation and/or a translation is an equivalence relation on T(P). We show that the dimension (in the topological sense) of the quotient set T(P)/ coincides with another parameter of P, namely, with its rank.Let V denote the set of vertices of P and let dp denote the distance on V defined by dp(u, v)=u–v ² for u, vV. Assouad [1] shows that dp belongs to the cone |V|:={d | _u,vV b _u b _v d(u,v) 0 for b ^V with _uV b _u = 1}. Then, the rank of P is defined as the dimension of the smallest face of the cone |V| that contains dp. AMS Subject Classification (1991): 11H06, 52C07.     

The Reflexive Dimension of a Lattice Polytope

The reflexive dimension refldim(P) of a lattice polytope P is the minimal integer d so that P is the face of some d-dimensional reflexive polytope. We show that refldim(P) is finite for every P, and give bounds for refldim(kP) in terms of refldim(P) and k. Received July 2, 2004     

A Polytope Approach to the Optimal Assembly Problem

The problem of assembling components into series modules to maximize the system reliability has been intensively studied in the literature. Invariably, the methods employed exploit special properties of the reliability function through standard analytical optimization techniques. We propose a geometric approach by exploiting the assembly polytope – a polytope generated by the potential assembly configurations. The new approach yields simpler proofs of known results, as well as new results about systems where the number of components in a module is not fixed, but subject to lower and upper bounds.     

Every Simplicial Polytope with at Most d + 4 Vertices Is a Quotient of a Neighborly Polytope

We show that every simplicial d-polytope with d+4 vertices is a quotient of a neighborly (2d+4)-polytope with 2d+8 vertices, using the technique of affine Gale diagrams. The result is extended to matroid polytopes. Received September 27, 1995.     

A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope

For a convex body B in a vector space V, we construct its approximation P_k, k =1 , 2, . . ., using an intersection of a cone of positive semidefinite quadratic forms with an affine subspace. We show that P_k is contained in B for each k. When B is the Symmetric Traveling Salesman Polytope on n cities T_n, we show that the scaling of P_k by n/k + O(1/n) contains T_n for . Membership for P_k is computable in time polynomial in n (of degree linear in k). We also discuss facets of T_n that lie on the boundary of P_k and we use eigenvalues to evaluate our bounds.     

The Integer Hull of a Convex Rational Polytope

Given $A\in\Z^{m\times n}$ and $b\in\Z^m$, we consider the integer program $\max \{cx\vert Ax=b;x\in\N^n\}$ and provide an {\it equivalent} and {\it explicit} linear program $\max \{\widehat{\xcc}q\vert \m q=r;q\geq 0\}$, where $\m,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $\p=\{x\in\R^n\vert Ax=b;x\geq0\}$. All strong valid inequalities can be obtained from the generators of a convex cone whose definition is explicit in terms of $\m$.     

Finding Small Triangulations of Polytope Boundaries Is Hard

We prove that it is NP-hard to decide whether a polyhedral 3-ball can be triangulated with k simplices. The construction also implies that it is difficult to find the minimal triangulation of such a 3-ball. A lifting argument is used to transfer the result also to triangulations of boundaries of 4-polytopes. The proof is constructive and translates a variant of the 3-SAT problem into an instance of a concrete polyhedral 3-ball for which it is difficult to find a minimal triangulation. Received February 17, 1999, and in revised form October 20, 1999. Online publication May 16, 2000.