Inequalities involving integrals of polar-conjugate concave functions

An inequality of K. Mahler, together with its case of equality, due to M. Meyer, are extended to integrals of powers of polar-conjugate concave functions. An application to estimation of the volume-product of certain convex bodies is given.     

Some inequalities involving medians of two simplexes

In this paper, some inequalities involving medians of two simplexes are established.     

The Schwan/Artin coordinatization for nearfield planes

Given any translation planeU, one can define the nucleusN as the subset of trace-preserving mappings of the point set satisfying a special linearity condition.N is always a nearfield isomorphic to the right-nucleus of a coordinatizing (left-)quasifield. If the transitivity axiom (NT) is valid,N is planar and the plane is isomorphic to the nearfield plane overN. Finally it is shown that (NT) is equivalent to the usual (P, OQ)-transitivity condition for nearfield planes.     

The spherical conjecture in Minkowski geometry

We show that the shapes of convex bodies containing m translates of a convex body K, so that their Minkowskian surface area is minimum, tends for growing m to a convex body L.Received: 7 January 2002     

A representation for volume involving interior reach

Supported by NSF Grant DMS-8802674     

Inequalities involving the inradii of simplexes

An inequality involving the inradii ofk-simplexes andl-simplexes (3 n) whose vertices lie in a finite set of points inE ⁿ has been proved in this paper.     

On four-colourings of the rational four-space

Summary LetQ ⁴ denote the graph, obtained from the rational points of the 4-space, by connecting two points iff their Euclidean distance is one. It has been known that its chromatic number is 4. We settle a problem of P. Johnson, showing that in every four-colouring of this graph, every colour class is every-where dense.     

Harmonic symmetrization of convex sets and of Finsler structures,with applications to Hilbert geometry

David Hilbert discovered in 1895 an important metric that is canonically associated to an arbitrary convex domain Ω$\Omega$ in the Euclidean (or projective) space. This metric is known to be Finslerian, and the usual proof of this fact assumes a certain degree of smoothness of the boundary of Ω$\Omega$, and refers to a theorem by Busemann and Mayer that produces the norm of a tangent vector from the distance function. In this paper, we develop a new approach for the study of the Hilbert metric where no differentiability is assumed. The approach exhibits the Hilbert metric on a domain as a symmetrization of a natural weak metric, known as the Funk metric. The Funk metric is described as a tautological   weak Finsler metric, in which the unit ball in each tangent space is naturally identified with the domain Ω$\Omega$ itself. The Hilbert metric is then identified with the reversible tautological weak Finsler structure   on Ω$\Omega$, and the unit ball of the Hilbert metric at each point is described as the harmonic symmetrization of the unit ball of the Funk metric. Properties of the Hilbert metric then follow from general properties of harmonic symmetrizations of weak Finsler structures.     

On a convex operator for finite sets

Let S be a finite set with m elements in a real linear space and let J_S be a set of m intervals in R. We introduce a convex operator co(S,J_S) which generalizes the familiar concepts of the convex hull, , and the affine hull, , of S. We prove that each homothet of that is contained in can be obtained using this operator. A variety of convex subsets of with interesting combinatorial properties can also be obtained. For example, this operator can assign a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For two types of families J_S we give two different upper bounds for the number of vertices of the polytopes produced as co(S,J_S). Our motivation comes from a recent improvement of the well-known Gauss-Lucas theorem. It turns out that a particular convex set co(S,J_S) plays a central role in this improvement.     

The steinitz lemma inl inf∞ sup2

Let (a, b) be a pair of non-negative numbers such that (1)a, b1 and (2)a+b3. Letu ₁,...,u _n be a sequence of vectors from the set {(x, y)R ²: |x|, |y|1}, withu ₁+...+u _n =0. It is shown that there is a permutation of indices such that all partial sumsu ₍₁₎+...+u _(k) lie in the rectangle |x|a, |y|b. Conditions (1) and (2) are also necessary.     

A vector-sum theorem in two-dimensional space

Given a finite setX of vectors from the unit ball of the max norm in the twodimensional space whose sum is zero, it is always possible to writeX = {x₁, , x_n} in such a way that the first coordinates of each partial sum lie in [–1, 1] and the second coordinates lie in [–C, C] whereC is a universal constant.     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

How many atoms can be defined by boxes?

We study the functionb(n, d), the maximal number of atoms defined byn d-dimensional boxes, i.e. parallelopipeds in thed-dimensional Euclidean space with sides parallel to the coordinate axes. We characterize extremal interval families definingb(n, 1)=2n-1 atoms and we show thatb(n, 2)=2n ²-6n+7. We prove that for everyd, exists and . Moreover, we obtainb*(3)=8/9.     

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Rubber bands,convex embeddings and graph connectivity

We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and physical properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ^k–1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium.As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allkn, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.     

Geradenanordnungen Mit Maximaler Anzahl Vierseitiger Flächen

Ohne Zusammenfassung

---

     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.