Barycentric coordinates for convex polytopes

An extension of the standard barycentric coordinate functions for simplices to arbitrary convex polytopes is described. The key to this extension is the construction, for a given convex polytope, of a unique polynomial associated with that polytope. This polynomial, theadjoint of the polytope, generalizes a previous two-dimensional construction described by Wachspress. The barycentric coordinate functions for the polytope are rational combinations of adjoints of various dual cones associated with the polytope.     

关于射影平坦Finsler空间

本文研究了射影平坦Finsler空间的几何量及其几何性质。证明了射影平坦Finsler空间的Ricci曲率可完全由射影因子简洁地刻画出来。同时还证明了，在射影平坦Finsler空间中，平均Berwald曲率S=0意味着Ricci曲率Ric是二次齐次的。此外，给出了一个射影平坦Finsler空间成为常曲率空间或局部Minkowski空间的充分条件。     

A construction for projectively unique polytopes

A method for constructing projectively unique polytopes with many vertices is described. The method makes use of the properties of Gale diagrams.     

On some projectively flat finsler metrics in terms of hypergeometric functions

This paper gives an explicit construction of a family of projectively flat Finsler metrics by using hypergeometric functions and a special class of projectively flat Randers metrics.     

Some classes of sprays in projective spray geometry

This paper studies some properties of projective changes in spray and Finsler geometry. Firstly, it obtains a comparison theorem on Ricci curvature for projectively related Finsler metrics. Secondly, it studies the properties of a class of projectively flat sprays, which particularly shows that there exist many isotropic sprays that cannot be induced by any (even singular) Finsler metrics.     

Projectively Equivalent Riemannian Spaces as Quasi-bi-Hamiltonian Systems

The class of Riemannian spaces admitting projectively, or geodesically, equivalent metrics is very closely related to a certain class of spaces for which the Hamilton–Jacobi equation for geodesics is separable. This fact is established, and its consequences explored, by showing that when a Riemannian space has a projectively equivalent metric its geodesic flow is a quasi-bi-Hamiltonian system. The existence of involutive first integrals of the geodesic flow, quadratic in the momenta, follows by a standard type of argument. When these integrals are independent they generate a Stäckel system.     

Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

Semigroup of matrices acting on the max-plus projective space

We investigate the action of semigroups of d×d matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.In terms of orbits, our main result states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most d! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton.This allows us to deduce the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.     

A projectively symmetric Finsler space

Symmetric (Riemannian) spaces were introduced and developed by Cartan [1, 2] which led to the discovery of projectively symmetric (Riemannian) spaces by Soós [9]. Recently the theory of symmetric spaces has been extended to Finsler geometry by the present author [5]. The current paper deals with that class of Finsler spaces throughout which their projective curvature tensors possess vanishing covariant derivatives. Following Soós' terminology such spaces are calledprojectively symmetric Finsler spaces. Examples, conditions for a symmetric Finsler space to be projectively symmetric, reduction of various identities, and the discussion of a decomposed projectively symmetric Finsler space form the skeleton of the paper.     

On projectively related Einstein metrics in Riemann-Finsler geometry

In this paper we study pointwise projectively related Einstein metrics (having the same geodesics as point sets). We show that pointwise projectively related Einstein metrics satisfy a simple equation along geodesics. In particular, we show that if two pointwise projectively related Einstein metrics are complete with negative Einstein constants, then one is a multiple of another. Received: 28 October 1999 / Revised: 10 January 2000 /Published online: 18 June 2001     

The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuéjols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.This work was initiated while the authors were visiting the Department of Statistics and Operations Research of New York University, and continued during several visits of the first author at IASI.     

When the degree sequence is a sufficient statistic

There is a uniquely defined random graph model with independent adjacencies in which the degree sequence is a sufficient statistic. The model was recently discovered independently by several authors. Here we join to the statistical investigation of the model, proving that if the degree sequence is in the interior of the polytope defined by the Erd?s–Gallai conditions, then a unique maximum likelihood estimate exists.     

Homogeneous spaces with invariant projectively flat affine connections

We characterize invariant projectively flat affine connections in terms of affine representations of Lie algebras, and show that a homogeneous space admits an invariant projectively flat affine connection if and only if it has an equivariant centro-affine immersion. We give a correspondence between semi-simple symmetric spaces with invariant projectively flat affine connections and central-simple Jordan algebras.

     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

Analytic centers and repelling inequalities

The new concepts of repelling inequalities, repelling paths, and prime analytic centers are introduced. A repelling path is a generalization of the analytic central path for linear programming, and we show that this path has a unique limit. Furthermore, this limit is the prime analytic center if the set of repelling inequalities contains only those constraints that “shape” the polytope. Because we allow lower dimensional polytopes, the proof techniques are non-standard and follow from data perturbation analysis. This analysis overcomes the difficulty that analytic centers of lower dimensional polytopes are not necessarily continuous with respect to the polytope's data representation. A second concept introduced here is that of the “prime analytic center”, in which we establish its uniqueness in the absence of redundant inequalities. Again, this is well known for full dimensional polytopes, but it is not immediate for lower dimensional polytopes because there are many different data representations of the same polytope, each without any redundant inequalities. These two concepts combine when we introduce ways in which repelling inequalities can interact.     

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.     

Two-edge connected spanning subgraphs and polyhedra

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303).     

On dually flat Finsler metrics

In this paper, we study the locally dually flat Finsler metrics which arise from information geometry. An equivalent condition of locally dually flat Finsler metrics is given. We find a new method to construct locally dually flat Finsler metrics by using a projectively flat Finsler metric under the condition that the projective factor is also a Finsler metric. Finally, we find that many known Finsler metrics are locally dually flat Finsler metrics determined by some projectively flat Finsler metrics.