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.     

Enumeration formulas for young tableaux in a diagonal strip

We derive combinatorial identities, involving the Bernoulli and Euler numbers, for the numbers of standard Young tableaux of certain skew shapes. This generalizes the classical formulas of D. André on the number of up-down permutations. The analysis uses a transfer operator approach extending the method of Elkies, combined with an identity expressing the volume of a certain polytope in terms of a Schur function.     

Leading coefficients of Morris type constant term identities

The Morris constant term identity is known to be equivalent to the famous Selberg integral. In this paper, we regard Morris type constant terms as polynomials of a certain parameter. Thus, we can take the leading coefficients and obtain new identities. These identities happen to be crucial in finding lower bounds for cardinalities of some restricted sumsets, and in calculating the volume of a Tesler polytope.     

Newton Polytopes and Witness Sets

We present two algorithms that compute the Newton polytope of a polynomial f defining a hypersurface \({\mathcal{H}}\) in \({\mathbb{C}^n}\) using numerical computation. The first algorithm assumes that we may only compute values of f—this may occur if f is given as a straight-line program, as a determinant, or as an oracle. The second algorithm assumes that \({\mathcal{H}}\) is represented numerically via a witness set. That is, it computes the Newton polytope of \({\mathcal{H}}\) using only the ability to compute numerical representatives of its intersections with lines. Such witness set representations are readily obtained when \({\mathcal{H}}\) is the image of a map or is a discriminant. We use the second algorithm to compute a face of the Newton polytope of the Lüroth invariant, as well as its restriction to that face.     

The doubly stochastic matrices of a vector majorization

Let y be majorized by x. We investigate the polytope of doubly stochastic matrices D for which y = Dx. We determine when there is a positive D and when there is a fully indecomposable D. We calculate the dimension of the polytope, and as a result determine when D is uniquely determined.     

The determinant expressions of some theta constant identities

In this paper, we derive two interesting theta constant identities by considering determinant structures. One of the two identities which we obtained is given by the Pfaffian, and the other is expressed by the resultant.     

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.     

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

Binary quadratic and cubic forms,and unipositive matrices

The classical method of reducing a positive binary quadratic form to a semi-reduced form applies translations alternately left and right to minimize the absolute value of the middle coefficient — and may therefore be called absolute reduction. There is an alternative method which keeps the sign of the middle coefficient constant before the end: we call this method positive reduction. Positive reduction seems to make possible an algorithm for finding the representations of 1 by a binary cubic form with real linear factors, and has various properties somewhat simpler than those of absolute reduction. Some of these properties involve unipositive matrices (with nonnegative integer elements and determinant 1). Certain semigroups of unipositive matrices with unique factorization into primes are described. Two of these semigroups give a neat approach to the reduction of indefinite binary quadratic forms—which may generalize. Some remarks on unimodular automorphs occur in Section 6.     

Relating single-scenario facets to the convex hull of the extensive form of a stochastic single-node flow polytope

We study when a facet-defining inequality for a deterministic, single-scenario subproblem is also facet-defining for the extensive form of a two-stage stochastic mixed-integer linear program (SMIP). To answer this question, we introduce a novel stochastic variant of the well-known single-node flow (SNF) polytope, and present necessary and sufficient conditions for single-scenario facet-defining inequalities to be facet-defining for the extensive form. We further demonstrate that our stochastic SNF polytope is a relaxation of a broad subclass of SMIPs, illustrating its generality.     

Polytopes of Minimum Positive Semidefinite Rank

The positive semidefinite (psd) rank of a polytope is the smallest $k$ k for which the cone of $k \times k$ k × k real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, and we characterize those polytopes whose psd rank equals this lower bound. We give several classes of polytopes that achieve the minimum possible psd rank including a complete characterization in dimensions two and three.     

Decomposition for adjustable robust linear optimization subject to uncertainty polytope

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max–min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.     

Mochizuki's indigenous bundles and Ehrhart polynomials

Mochizuki's work on torally indigenous bundles [1] yields combinatorial identities by degenerating to different curves of the same genus. We rephrase these identities in combinatorial language and strengthen them, giving relations between Ehrhart quasi-polynomials of different polytopes. We then apply the theory of Ehrhart quasi-polynomials to conclude that the number of dormant torally indigenous bundles on a general curve of a given type is expressed as a polynomial in the characteristic of the base field. In particular, we conclude the same for the number vector bundles of rank two and trivial determinant whose Frobenius-pullbacks are maximally unstable, as well as self-maps of the projective line with prescribed ramification. The second author was supported by a fellowship from the Japan Society for the Promotion of Science during the preparation of this paper.     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

Handelman’s hierarchy for the maximum stable set problem

The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope with non-empty interior can be represented as conic combination of products of the linear constraints defining the polytope. We relate the rank of Handelman’s hierarchy with structural properties of graphs. In particular we show a relation to fractional clique covers which we use to upper bound the Handelman rank for perfect graphs and determine its exact value in the vertex-transitive case. Moreover we show two upper bounds on the Handelman rank in terms of the (fractional) stability number of the graph and compute the Handelman rank for several classes of graphs including odd cycles and wheels and their complements. We also point out links to several other linear and semidefinite programming hierarchies.     

Plane partitions VI: Stembridge's TSPP theorem

We provide a new proof of Stembridge's theorem which validated the Totally Symmetric Plane Partitions (TSPP) Conjecture. The overall strategy of our proof follows the same general pattern of determinant evaluation as discussed by the first named author in a series of papers. The resulting hypergeometric multiple sum identities turn out to be quite complicated. Their correctness is proved by applying new algorithmic methods from symbolic summation.     

A universality theorem for projectively unique polytopes and a conjecture of Shephard

We prove that every polytope described by algebraic coordinates is the face of a projectively unique polytope. This provides a universality property for projectively unique polytopes. Using a closely related result of Below, we construct a combinatorial type of 5-dimensional polytope that is not realizable as a subpolytope of any stacked polytope. This disproves a classical conjecture in polytope theory, first formulated by Shephard in the seventies.     

Combinatorial proofs of an identity from Ramanujan’s lost notebook and its variations

We give two combinatorial proofs and partition-theoretic interpretations of an identity from Ramanujan’s lost notebook. We prove a special case of the identity using the involution principle. We then extend this into a direct proof of the full identity using a generalization of the involution principle. We also show that the identity can be rewritten into a modified form that we prove bijectively. This fits the identity into Pak’s duality of partition identities proven using the involution principle and partition identities proven bijectively. The original identity was first proven algebraically by Andrews as a consequence of an identity of Rogers’ and combinatorially by Kim, while the modified form of the identity generalizes an identity recently found by Andrews and Warnaar related to the product of partial theta functions.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.