The Busemann-Petty problem via spherical harmonics

The Busemann-Petty problem asks whether symmetric convex bodies in with smaller central hyperplane sections necessarily have smaller n-dimensional volume. The solution has recently been completed, and the answer is affirmative if n?4 and negative if n?5. In this article we present a short proof of the affirmative result and its generalization using the Funk-Hecke formula for spherical harmonics.     

Comparison of volumes of convex bodies in real, complex, and quaternionic spaces

The classical Busemann-Petty problem (1956) asks, whether origin-symmetric convex bodies in Rn with smaller hyperplane central sections necessarily have smaller volumes. It is known, that the answer is affirmative if n?4 and negative if n>4. The same question can be asked when volumes of hyperplane sections are replaced by other comparison functions having geometric meaning. We give unified analysis of this circle of problems in real, complex, and quaternionic n-dimensional spaces. All cases are treated simultaneously. In particular, we show that the Busemann-Petty problem in the quaternionic n-dimensional space has an affirmative answer if and only if n=2. The method relies on the properties of cosine transforms on the unit sphere. We discuss possible generalizations.     

A solution to the lower dimensional Busemann-Petty problem in the hyperbolic space

The lower dimensional Busemann-Petty problem asks whether origin symmetric convex bodies in ℝⁿ with smaller volume of all k-dimensional sections necessarily have smaller volume. As proved by Bourgain and Zhang, the answer to this question is negative if k>3. The problem is still open for k = 2, 3. In this article we formulate and completely solve the lower dimensional Busemann-Petty problem in the hyperbolic space ℍⁿ.     

Projection problems for symmetric polytopes

Let K⊂Rn be a convex body (a compact, convex subset with non-empty interior), ΠK its projection body. Finding the least upper bound, as K ranges over the class of origin-symmetric convex bodies, of the affine-invariant ratio V(ΠK)/V(K)ⁿ⁻¹, being called Schneider's projection problem, is a well-known open problem in the convex geometry. To study this problem, Lutwak, Yang and Zhang recently introduced a new affine invariant functional for convex polytopes in Rn. For origin-symmetric convex polytopes, they posed a conjecture for the new functional U(P). In this paper, we give an affirmative answer to the conjecture in Rn, thereby, obtain a modified version of Schneider's projection problem.     

Extremum problems for the cone volume functional of convex polytopes

Lutwak, Yang and Zhang defined the cone volume functional U over convex polytopes in Rn containing the origin in their interiors, and conjectured that the greatest lower bound on the ratio of this centro-affine invariant U to volume V is attained by parallelotopes. In this paper, we give affirmative answers to the conjecture in R² and R³. Some new sharp inequalities characterizing parallelotopes in Rn are established. Moreover, a simplified proof for the conjecture restricted to the class of origin-symmetric convex polytopes in Rn is provided.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

On the number of halving planes

LetS ³ be ann-set in general position. A plane containing three of the points is called a halving plane if it dissectsS into two parts of equal cardinality. It is proved that the number of halving planes is at mostO(n ^2.998).As a main tool, for every setY ofn points in the plane a setN of sizeO(n ⁴) is constructed such that the points ofN are distributed almost evenly in the triangles determined byY.Research supported partly by the Hungarian National Foundation for Scientific Research grant No. 1812     

On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}. A mapping p:V→R^r, where p¹,…,pⁿ are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in R^r, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in R^r is said to be dimensionally rigid iff there does not exist a framework G(q) in R^s for s?r+1, such that ∥qⁱ-q^j∥²=∥pⁱ-p^j∥² for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p¹,…,pⁿ of the given r-configuration are in general position, is also investigated.     

On the smallest disk containing a planar reduced convex body

A convex body R of Euclidean space E ^d is said to be reduced if every convex body $ P \subset R $ different from R has thickness smaller than the thickness $ \Delta(R) $ of R. We prove that every planar reduced body R is contained in a disk of radius $ {1\over 2}\sqrt 2 \cdot \Delta(R) $. For $ d \geq 3 $, an analogous property is not true because we can construct reduced bodies of thickness 1 and of arbitrarily large diameter.     

Integer cells in convex sets

Every convex body K in Rⁿ has a coordinate projection PK that contains at least cells of the integer lattice PZⁿ, provided this volume is at least one. Our proof of this counterpart of Minkowski's theorem is based on an extension of the combinatorial density theorem of Sauer, Shelah and Vapnik-Chervonenkis to Zⁿ. This leads to a new approach to sections of convex bodies. In particular, fundamental results of the asymptotic convex geometry such as the Volume Ratio Theorem and Milman's duality of the diameters admit natural versions for coordinate sections.     

Spectral criteria for complementary triangular forms

In this paper we consider the following problem: Given two matricesA,Z∈? ^n×n , does there exist an invertiblen×n-matrixS such thatS ^?1 AS is an upper triangular matrix andS ^?1 ZS is a lower triangular matrix, and if so, what can be said about the order in which the eigenvalues ofA andZ appear on the diagonals of these triangular matrices? For special choices ofA andZ a complete solution is possible, as has been shown by several authors. Here we follow a lead, provided by Shmuel Friedland, who discussed the case where bothA andZ have at leastn-1 linearly independent eigenvectors, and we descibe the problem in terms of Jordan chains and left-Jordan chains for the matricesA, Z. The results give some insight in the question why certain classes of matrices (like the nonderogatory and the rank 1 matrices) allow for a detailed solution of the problems described above; for some of these classes the result of this analysis is presented here for the first time.     

Necessary and sufficient conditions for hyperplane transversals

We prove that a finite family ={B ₁,B ₂, ...,B _n } of connected compact sets in ^d has a hyperplane transversal if and only if for somek there exists a set of pointsP={p ₁,p ₂, ...,p _n } (i.e., ak-dimensional labeling of the family) which spans ^k and everyk+2 sets of are met by ak-flat consistent with the order type ofP. This is a common generalization of theorems of Hadwiger, Katchalski, Goodman-Pollack and Wenger.Supported in part by NSF grant DMS-8501947 and CCR-8901484, NSA grant MDA904-89-H-2030, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648.Supported by the National Science and Engineering Research Council of Canada and DIMACS.     

On the nonnegative rank of Euclidean distance matrices

The Euclidean distance matrix for n distinct points in R^r is generically of rank r + 2. It is shown in this paper via a geometric argument that its nonnegative rank for the case r = 1 is generically n.     

Integral geometry for the 1-norm

Classical integral geometry takes place in Euclidean space, but one can attempt to imitate it in any other metric space. In particular, one can attempt this in Rⁿ${\mathbb{R}}^n$ equipped with the metric derived from the p  -norm. This has, in effect, been investigated intensively for 1<p<∞$1<p<\infty$, but not for p=1$p=1$. We show that integral geometry for the 1-norm bears a striking resemblance to integral geometry for the 2-norm, but is radically different from that for all other values of p  . We prove a Hadwiger-type theorem for Rⁿ${\mathbb{R}}^n$ with the 1-norm, and analogues of the classical formulas of Steiner, Crofton and Kubota. We also prove principal and higher kinematic formulas. Each of these results is closely analogous to its Euclidean counterpart, yet the proofs are quite different.     

The Dirichlet Markov Ensemble

We equip the polytope of n×n Markov matrices with the normalized trace of the Lebesgue measure of Rⁿ². This probability space provides random Markov matrices, with i.i.d. rows following the Dirichlet distribution of mean (1/n,…,1/n). We show that if is such a random matrix, then the empirical distribution built from the singular values of tends as n→∞ to a Wigner quarter-circle distribution. Some computer simulations reveal striking asymptotic spectral properties of such random matrices, still waiting for a rigorous mathematical analysis. In particular, we believe that with probability one, the empirical distribution of the complex spectrum of tends as n→∞ to the uniform distribution on the unit disc of the complex plane, and that moreover, the spectral gap of is of order when n is large.     

Constructing a polytope to approximate a convex body

We develop an algorithm to construct a convex polytopeP withn vertices, contained in an arbitrary convex bodyK inR ^d , so that the ratio of the volumes |K/P|/|K| is dominated byc ·. d/n ^2/(d–1).Supported in part by the fund for the promotion of research in the Technion     

Capacities, surface area, and radial sums

A dual capacitary Brunn-Minkowski inequality is established for the (n−1)-capacity of radial sums of star bodies in Rn. This inequality is a counterpart to the capacitary Brunn-Minkowski inequality for the p-capacity of Minkowski sums of convex bodies in Rn, 1?p<n, proved by Borell, Colesanti, and Salani. When n?3, the dual capacitary Brunn-Minkowski inequality follows from an inequality of Bandle and Marcus, but here a new proof is given that provides an equality condition. Note that when n=3, the (n−1)-capacity is the classical electrostatic capacity. A proof is also given of both the inequality and a (different) equality condition when n=2. The latter case requires completely different techniques and an understanding of the behavior of surface area (perimeter) under the operation of radial sum. These results can be viewed as showing that in a sense (n−1)-capacity has the same status as volume in that it plays the role of its own dual set function in the Brunn-Minkowski and dual Brunn-Minkowski theories.     

On visualization scaling, subeigenvectors and Kleene stars in max algebra

The purpose of this paper is to investigate the interplay arising between max algebra, convexity and scaling problems. The latter, which have been studied in nonnegative matrix theory, are strongly related to max algebra. One problem is that of strict visualization scaling, defined as, for a given nonnegative matrix A, a diagonal matrix X such that all elements of X^-1AX are less than or equal to the maximum cycle geometric mean of A, with strict inequality for the entries which do not lie on critical cycles. In this paper such scalings are described by means of the max algebraic subeigenvectors and Kleene stars of nonnegative matrices as well as by some concepts of convex geometry.