Some characterisations of the ellipsoid

We show that a convex bodyK of dimensiond≧3 is an ellipsoid if it has any of the following properties: (1) the “grazes” of all points close toK are flat, (2) all sections of small diameter are centrally symmetric, (3) parallel (d−1)-sections close to the boundary are width-equivalent, (4)K is strictly convex and all (d−1)-sections close to the boundary are centrally symmetric; the last two results are deduced from their 3-dimensional cases which were proved by Aitchison.     

Dimension Gaps between Representability and Collapsibility

A simplicial complex K\mathsf{K} is called d -representable if it is the nerve of a collection of convex sets in ℝ ^d ; K\mathsf{K} is d -collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d−1 that is contained in a unique maximal face; and K\mathsf{K} is d -Leray if every induced subcomplex of K\mathsf{K} has vanishing homology of dimension d and larger. It is known that d-representable implies d-collapsible implies d-Leray, and no two of these notions coincide for d≥2. The famous Helly theorem and other important results in discrete geometry can be regarded as results about d-representable complexes, and in many of these results, “d-representable” in the assumption can be replaced by “d-collapsible” or even “d-Leray.”     

On-line covering a cube by a sequence of cubes

A procedure for packing or covering a given convex bodyK with a sequence of convex bodies {C _i} is anon-line method if the setC _i are given in sequence. andC _i+1 is presented only afterC _i has been put in place, without the option of changing the placement afterward. The “one-line” idea was introduced by Lassak and Zhang [6] who found an asymptotic volume bound for the problem of on-line packing a cube with a sequence of convex bodies. In this note a problem of Lassak is solved, concerning on-line covering a cube with a sequence of cubes, by proving that every sequence of cubes in the Euclidean spaceE ^d whose total volume is greater than 4 ^d admits an on-line covering of the unit cube. Without the “on-line” restriction, the best possible volume bound is known to be 2 ^d −1, obtained by Groemer [2] and, independently, by Bezdek and Bezdek [1]. The on-line covering method described in this note is based on a suitable cube-filling Peano curve.     

Convex polytopes whose projection bodies and difference sets are polars

In a paper by the author and B. Weissbach it was proved that the projection body and the difference set of ad-simplex (d≥2) are polars. Obviously, ford=2 a convex domain has this property if and only if its difference set is bounded by a so-called Radon curve. A natural question emerges about further classes of convex bodies inR ^d (d≥3) inducing the mentioned polarity. The aim of this paper is to show that a convexd-polytope (d≥3) is a simplex if and only if its projection body and its difference set are polars.     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

Star-shaped sets in normed spaces

We prove a generalization of the Krasnosel’ski theorem on star-shaped sets. Usingd-segments inn-dimensional Minkowski spaces instead of usual segments, the notions “d-visibility” and “d-star-shapedness” are introduced. Our main aim is to give necessary and sufficient conditions ford-star-shapedness in finite-dimensional normed spaces.     

Zonotopes with Large 2D-Cuts

There are d-dimensional zonotopes with n zones for which a 2-dimensional central section has Ω(n ^d−1) vertices. For d=3, this was known, with examples provided by the “Ukrainian easter eggs” by Eppstein et al. Our result is asymptotically optimal for all fixed d≥2.     

<Emphasis Type="Italic">f</Emphasis>-Vectors of barycentric subdivisions

For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney–Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope. For a general (d − 1)-dimensional simplicial complex Δ the h-polynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this h-polynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d. F. Brenti and V. Welker are partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.     

Formulae and growth rates of high-dimensional polycubes

A d-dimensional polycube is a facet-connected set of cubes in d dimensions. Fixed polycubes are considered distinct if they differ in their shape or orientation. A proper d-dimensional polycube spans all the d dimensions, that is, the convex hull of the centers of its cubes is d-dimensional. In this paper we prove rigorously some (previously conjectured) closed formulae for fixed (proper and improper) polycubes, and show that the growth-rate limit of the number of polycubes in d dimensions is 2ed−o(d). We conjecture that it is asymptotically equal to (2d−3)e+O(1/d).     

Shortest billiard trajectories

In this paper we prove that any convex body of the d-dimensional Euclidean space (d ≥ 2) possesses at least one shortest generalized billiard trajectory moreover, any of its shortest generalized billiard trajectories is of period at most d + 1. Actually, in the Euclidean plane we improve this theorem as follows. A disk-polygon with parameter r > 0 is simply the intersection of finitely many (closed) circular disks of radii r, called generating disks, having some interior point in common in the Euclidean plane. Also, we say that a disk-polygon with parameter r > 0 is a fat disk-polygon if the pairwise distances between the centers of its generating disks are at most r. We prove that any of the shortest generalized billiard trajectories of an arbitrary fat disk-polygon is a 2-periodic one. Also, we give a proof of the analogue result for ε-rounded disk-polygons obtained from fat disk-polygons by rounding them off using circular disks of radii ε > 0. Our theorems give partial answers to the very recent question raised by S. Zelditch on characterizing convex bodies whose shortest periodic billiard trajectories are of period 2. K. Bezdek partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Infinitesimal Rigidity of Convex Polytopes

Aleksandrov [1] proved that a simple convex d -dimensional polytope, d ≥ 3 , is infinitesimally rigid if the volumes of its facets satisfy a certain assumption of stationarity. We extend this result by proving that this assumption can be replaced by a stationarity assumption on the k -dimensional volumes of the polytope's k -dimensional faces, where k ∈{1,. . .,d-1} . Received November 20, 1997.     

Steiner symmetrals and their distance from a ball

It is known that given any convex bodyK ⊂ ℝ ⁿ there is a sequence of suitable iterated Steiner symmetrizations ofK that converges, in the Hausdorff metric, to a ball of the same volume. Hadwiger and, more recently, Bourgain, Lindenstrauss and Milman have given estimates from above of the numberN of symmetrizations necessary to transformK into a body whose distance from the equivalent ball is less than an arbitrary positive constant. In this paper we will exhibit some examples of convex bodies which are “hard to make spherical”. For instance, for any choice of positive integersn≥2 andm, we construct ann-dimensional convex body with the property that any sequence ofm symmetrizations does not decrease its distance from the ball. A consequence of these constructions are some lower bounds on the numberN.     

On the volume functional of compact manifolds with boundary with constant scalar curvature

We study the volume functional on the space of constant scalar curvature metrics with a prescribed boundary metric. We derive a sufficient and necessary condition for a metric to be a critical point, and show that the only domains in space forms, on which the standard metrics are critical points, are geodesic balls. In the zero scalar curvature case, assuming the boundary can be isometrically embedded in the Euclidean space as a compact strictly convex hypersurface, we show that the volume of a critical point is always no less than the Euclidean volume bounded by the isometric embedding of the boundary, and the two volumes are equal if and only if the critical point is isometric to a standard Euclidean ball. We also derive a second variation formula and apply it to show that, on Euclidean balls and “small” hyperbolic and spherical balls in dimensions 3 ≤ n ≤ 5, the standard space form metrics are indeed saddle points for the volume functional.     

Finite sphere packing and sphere covering

A basic problem of finite packing and covering is to determine, for a given number ofk unit balls in Euclideand-spaceE ^d , (1) the minimal volume of all convex bodies into which thek balls can be packed and (2) the maximal volume of all convex bodies which can be covered by thek balls. In the sausage conjectures by L. Fejes Tóth and J. M. Wills it is conjectured that, for alld5, linear arrangements of thek balls are best possible. In the paper several partial results are given to support both conjectures. Furthermore, some relations between finite and infinite (space) packing and covering are investigated.This paper was written while the first named author was visiting the Forschungsinstitut für Geistes- und Sozialwissenschaften at the University of Siegen.     

An on-line potato-sack theorem

We discuss packings of sequences of convex bodies of Euclideann-spaceE ⁿ in a box and particularly in a cube. Following an Auerbach-Banach-Mazur-Ulam problem from the well-knownScottish Book, results of this kind are called potato-sack theorems. We consider on-line packing methods which work under the restriction that during the packing process we are given each succeeding “potato” only when the preceding one has been packed. One of our on-line methods enables us to pack into the cube of sided>1 inE ⁿ every sequence of convex bodies of diameters at most 1 whose total volume does not exceed ( ). Asymptotically, asd→∞, this volume is as good as that given by the non-on-line methods previously known. This research was done during the academic year 1987/88, while the first author was visiting the City College of the City University of New York. The second author was supported in part by Office of Naval Research Grant N00014-85-K-0147.     

The modified complex Busemann-Petty problem on sections of convex bodies

The complex Busemann-Petty problem asks whether origin symmetric convex bodies in with smaller central hyperplane sections necessarily have smaller volume. The answer is affirmative if n ≤ 3 and negative if n ≥ 4. Since the answer is negative in most dimensions, it is natural to ask what conditions on the (n − 1)-dimensional volumes of the central sections of complex convex bodies with complex hyperplanes allow to compare the n-dimensional volumes. In this article we give necessary conditions on the section function in order to obtain an affirmative answer in all dimensions. The result is the complex analogue of [16].      

An example of a convex body without symmetric projections

Many crucial results of the asymptotic theory of symmetric convex bodies were extended to the non-symmetric case in recent years. That led to the conjecture that for everyn-dimensional convex bodyK there exists a projectionP of rankk, proportional ton, such thatPK is almost symmetric. We prove that the conjecture does not hold. More precisely, we construct ann-dimensional convex bodyK such that for everyk >C√nlnn and every projectionP of rankk, the bodyPK is very far from being symmetric. In particular, our example shows that one cannot expect a formal argument extending the “symmetric” theory to the general case. This author holds a Lady Davis Fellowship.     

Some combinatorial properties of flag simplicial pseudomanifolds and spheres

A simplicial complex Δ is called flag if all minimal nonfaces of Δ have at most two elements. The following are proved: First, if Δ is a flag simplicial pseudomanifold of dimension d−1, then the graph of Δ (i) is (2d−2)-vertex-connected and (ii) has a subgraph which is a subdivision of the graph of the d-dimensional cross-polytope. Second, the h-vector of a flag simplicial homology sphere Δ of dimension d−1 is minimized when Δ is the boundary complex of the d-dimensional cross-polytope.     

Lower bounds to helly numbers of line transversals to disjoint congruent balls

A line ℓ is a transversal to a family F of convex objects in ℝ ^d if it intersects every member of F. In this paper we show that for every integer d ⩾ 3 there exists a family of 2d−1 pairwise disjoint unit balls in ℝ ^d with the property that every subfamily of size 2d − 2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957. Crucial to the proof is the notion of a pinned transversal, which means an isolated point in the space of transversals. Here we investigate minimal pinning configurations and construct a family F of 2d−1 disjoint unit balls in ℝ ^d with the following properties: (i) The space of transversals to F is a single point and (ii) the space of transversals to any proper subfamily of F is a connected set with non-empty interior.     

On lattice points in polyhedral cross-sections

(a) We prove that the convex hull of anyk ^d +1 points of ad-dimensional lattice containsk+1 collinear lattice points. (b) For a convex polyhedron we consider the numbers of its lattice points in consecutive parallel lattice hyperplanes (levels). We prove that if a polyhedron spans no more than 2 ^d−1 levels, then this string of numbers may be arbitrary. On the other hand, we give an example of a string of 2 ^d−1+1 numbers to which no convex polyhedron corresponds inR ^d .