Facets of the linear ordering polytope

LetD _n be the complete digraph onn nodes, and letP _LO ⁿ denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD _n (i.e. these are exactly the acyclic tournaments ofD _n ). We show that various classes of inequalities define facets ofP _LO ⁿ , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.     

Fence facets from non-regular graphs for the linear ordering polytope

We present a new class of facet defining inequalities for the linear ordering polytope. The underlying graphs of these new inequalities are non-regular (have vertices of different degrees); the other known classes of fence inequalities are induced by regular graphs.     

On integral Apollonian circle packings

The curvatures of four mutually tangent circles with disjoint interiors form what is called a Descartes quadruple. The four least curvatures in an integral Apollonian circle packing form what is called a root Descartes quadruple and, if the curvatures are relatively prime, we say that it is a primitive root quadruple. We prove a conjecture of Mallows by giving a closed formula for the number of primitive root quadruples with minimum curvature −n. An Apollonian circle packing is called strongly integral if every circle has curvature times center a Gaussian integer. The set of all such circle packings for which the curvature plus curvature times center is congruent to 1 modulo 2 is called the “standard supergasket.” Those centers in the unit square are in one-to-one correspondence with the primitive root quadruples and exhibit certain symmetries first conjectured by Mallows. We prove these symmetries; in particular, the centers are symmetric around y=x if n is odd, around x=1/2 if n is an odd multiple of 2, and around y=1/2 if n is a multiple of 4.     

On the ratio of optimal integral and fractional covers

It is shown that the ratio of optimal integral and fractional covers of a hypergraph does not exceed 1 + log d, where d is the maximum degree. This theorem may replace probabilistic methods in certain circumstances. Several applications are shown.     

On linear sections of lattice packings

Ind-dimensional euclidean spaceE ^d letP be a lattice packing of subsets ofE ^d , and letH be ak-dimensional linear subspace ofE ^d (0<k<d). Then,P induces a packing inH consisting of all setsPH withPP. The relationship between the density of this packing inH and the density ofP is investigated. A result from the theory of uniform distribution of linear forms is used to prove an integral formula that enables one to evaluate the density of the induced packing inH (under suitable assumptions on the sets ofP and the functionals used to define the densities). It is shown that this result leads to explicit formulas for the averages of the induced densities under the rotation ofH. If the densities are taken with respect to the mean cross-sectional measures of convex bodies one obtains analogues of the integral geometric intersection formulas of Crofton.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthdaySupported by National Science Foundation Research Grant DMS 8300825.     

Minimal covers,minimal sets and canonical facets of the posynomial knapsack polytope

An irredundant representation of the 0–1 solutions to a posynomial inequality in terms of covering constraints induced by minimal covers is given. This representation is further strengthened using extended covering constraints induced by maximal extensions of minimal covers. Necessary, sufficient, and in a special case necessary and sufficient conditions for an extended covering constraint induced by a minimal set to be a facet of the posynomial knapsack polytope are given.     

On the cut polytope

The cut polytopeP _C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP _C (G). We describe three methods with which new facet-defining inequalities ofP _C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP _C (G) ifG is not contractible toK ₅. We give a simple characterization of adjacency inP _C (G) and prove that for complete graphs this polytope has diameter one and thatP _C (G) has the Hirsch property. A relationship betweenP _C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.     

On integral representations of linear forms

Starting from a given *-algebra, we consider integral representations of positive linear forms on the hermitian spectrum of the algebra, providing necessary and sufficient conditions theorem. This specializes to previous results of R. S. Bucy—G. Maltese and G. Maltese for Banach *-algebras, and M. Fragoulopoulou for Imc *-algebras.     

On the truncated assignment polytope

We investigate the convex polytope Ω_m,n(r) which is the convex hull of the m × nr-subpermutation matrices. The faces of Ω_m,n(r) are characterized, and formulae are obtained to compute their dimensions. The faces of Ω_m,n(r) are themselves convex polytopes, and we determine their facets.     

On the acyclic subgraph polytope

The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.     

New polytope decompositions and Euler-Maclaurin formulas for simple integral polytopes

We give new weighted decompositions for simple polytopes, generalizing previous results of Lawrence-Varchenko and Brianchon-Gram. We start with Witten's non-abelian localization principle in equivariant cohomology for the norm-square of the moment map in the context of toric varieties to obtain a decomposition for Delzant polytopes. Then, by a purely combinatorial argument, we show that this formula holds for any simple polytope. As an application, we study Euler-Maclaurin formulas.     

On linear integral operators with nonnegative kernels

Let K be an eventually compact linear integral operator on $\text{L}{}^{\mathrm{p}}\text{(Ω, μ), 1 ? p < ∞}$, with nonnegative kernel k(x, y), where the underlying measure μ is totally σ-finite on the domain set Ω when p = 1. In considering the equation λf = Kf + g for given nonnegative $\text{g ? L}{}^{\mathrm{p}}\text{(Ω, μ), λ > 0}$, P. Nelson, Jr. provided necessary and sufficient conditions, in terms of the support of g, such that a nonnegative solution $\text{f ? L}{}^{\mathrm{p}}\text{(Ω, μ)}$ was attained. Such conditions led to generalizing some of the graph-theoretic ideas associated with the normal form of a nonnegative reducible matrix. The purpose of this paper is to show that the analysis by Nelson can be enlarged to provide a more complete generalization of the normal form of a nonnegative matrix which can be used to characterize the distinguished eigenvalues of K and K¹, and to describe sets of support for the eigenfunctions and generalized eigenfunctions of both K and K¹ belonging to the spectral radius of K.     

On linear differential games with integral constraints

The paper is devoted to quasilinear conflict-controlled processes of general form with a cylindrical terminal set. A specific feature is that, instead of a dynamical system, we start with representation of a solution in a form that allows one to include an additive term with the initial data and a control unit. This makes it possible to consider a broad spectrum of dynamic processes in a unified scheme. Our study is based on the method of resolving functions. We obtain sufficient conditions for the solvability of the pursuit problem at a certain guaranteed time in the class of strategies that use information on the behavior of the opponent in the past, as well as in the class of stroboscopic strategies. We also find conditions under which information on the prehistory of the evader does not matter. The guaranteed times of various schemes of the resolving function method are compared with the guaranteed time of Pontryagin’s first direct method. The qualitative results are illustrated by an example of a game problem with simple motions and incomplete sweeping for special control domains in the Pontryagin condition.     

On the general routing polytope

The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467-481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP.