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.     

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.     

Balanced complexes and complexes without large missing faces

The face numbers of simplicial complexes without missing faces of dimension larger than i are studied. It is shown that among all such (d−1)-dimensional complexes with non-vanishing top homology, a certain polytopal sphere has the componentwise minimal f-vector; and moreover, among all such 2-Cohen–Macaulay (2-CM) complexes, the same sphere has the componentwise minimal h-vector. It is also verified that the l-skeleton of a flag (d−1)-dimensional 2-CM complex is 2(d−l)-CM, while the l-skeleton of a flag piecewise linear (d−1)-sphere is 2(d−l)-homotopy CM. In addition, tight lower bounds on the face numbers of 2-CM balanced complexes in terms of their dimension and the number of vertices are established.     

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).     

Covering Convex Bodies by Cylinders and Lattice Points by Flats

In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 1≤k≤d−1. K. Bezdek and A.E. Litvak are partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Convex subdivisions with low stabbing numbers

It is shown that for every subdivision of the d-dimensional Euclidean space, d ≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n/log log n)^1/(d−1)) cells. In other words, if a convex subdivision of d-space has the property that any line stabs at most k cells, then the subdivision has at most exp(O(k ^d−1 log k)) cells. This bound is best possible apart from a constant factor. It was previously known only in the case d = 2. Supported in part by NSERC grant RGPIN 35586.     

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.     

Phase space,wavelet transform and Toeplitz-Hankel type operators

Domain constants are numbers attached to regions in the complex plane ℂ. For a region Ω in ℂ, letd(Ω) denote a generic domain constant. If there is an absolute constantM such thatM ⁻¹≤d(Ω)/d(Δ)≤M whenever Ω and Δ are conformally equivalent, then the domain constant is called quasiinvariant under conformal mappings. IfM=1, the domain constant is conformally invariant. There are several standard problems to consider for domain constants. One is to obtain relationships among different domain constants. Another is to determine whether a given domain constant is conformally invariant or quasi-invariant. In the latter case one would like to determine the best bound for quasi-invariance. We also consider a third type of result. For certain domain constants we show there is an absolute constantN such that |d(Ω)−d(Δ)|≤N whenever Ω and Δ and conformally equivalent, sometimes determing the best possible constantN. This distortion inequality is often stronger than quasi-invariance. We establish results of this type for six domain constants. Research partially supported by a National Science Foundation Grant.     

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

ALMOST EQUIDISTANT POINTS ON S D-1

Let S ^d-1 denote the (d − 1)-dimensional unit sphere centered at the origin of the d-dimensional Euclidean space. Let 0 < α < π. A set P of points in S ^d-1 is called almost α-equidistant if among any three points of P there is at least one pair lying at spherical distance α. In this note we prove upper bounds on the cardinality of P depending only on d. This revised version was published online in August 2006 with corrections to the Cover Date.     

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

Construction of Optimal Cubature Formulas Related to?Computer Tomography

We study the problem of the optimization of approximate integration on the class of functions defined on the parallelepiped Π _d =[0,a ₁]×⋅⋅⋅×[0,a _d ], a ₁,…,a _d >0, having a given majorant for the modulus of continuity (relative to the l ₁-metric in ℝ ^d ). An optimal cubature formula, which uses as information integrals of f along intersections of Π _d with n arbitrary (d−1)-dimensional hyperplanes in ℝ ^d (d>1) is obtained. We also find an asymptotically optimal sequence of cubature formulas, whose information functionals are integrals of f along intersections of Π _d with shifts of (d−2)-dimensional coordinate subspaces of ℝ ^d (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.     

The gonality of smooth curves with plane models

LetC be the normalization of an integral plane curve of degreed with δ ordinary nodes or cusps as its singularities. If δ=0, then Namba proved that there is no linear seriesg _d ^−2/1 and that everyg _d ^−1/1 is cut out by a pencil of lines passing through a point onC. The main purpose of this paper is to generalize his result to the case δ>0. A typical one is as follows: Ifd≥2(k+1), and δ<kd−(k+1)²+3 for somek>0, thenC has no linear seriesg _d ^−3/1 . We also show that ifd≥2k+3 and δ<kd−(k+1)²+2, then each linear seriesg _d ^−2/1 onC is cut out by a pencil of lines. We have similar results forg _d ^−1/1 andg _2d ^−9/1 . Furthermore, we also show that all of our theorems are sharp.     

Absolute continuity of the spectrum of the periodic Schrödinger operator in a layer and in a smooth cylinder

The Schr?dinger operator H = −Δ + V is considered in a layer or in a d-dimensional cylinder. The potential V is assumed to be periodic with respect to a lattice. The absolute continuity of H is established, provided that V ∈ L _p,loc, where p is a real number greater than d/2 in the case of a layer and p > max(d/2, d − 2) for a cylinder. Bibliography: 14 titles.     

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

A finite element method for surface PDEs: matrix properties

We consider a recently introduced new finite element approach for the discretization of elliptic partial differential equations on surfaces. The main idea of this method is to use finite element spaces that are induced by triangulations of an “outer” domain to discretize the partial differential equation on the surface. The method is particularly suitable for problems in which there is a coupling with a problem in an outer domain that contains the surface, for example, two-phase flow problems. It has been proved that the method has optimal order of convergence both in the H ¹ and in the L ²-norm. In this paper, we address linear algebra aspects of this new finite element method. In particular the conditioning of the mass and stiffness matrix is investigated. For the two-dimensional case we present an analysis which proves that the (effective) spectral condition number of the diagonally scaled mass matrix and the diagonally scaled stiffness matrix behaves like h ⁻³| ln h| and h ⁻²| ln h|, respectively, where h is the mesh size of the outer triangulation.     

Kähler hyperbolicity and the Euler number of a compact manifold with geodesic flow of Anosov type

 Let M be a 2m-dimensional compact Riemannian manifold with Anosov geodesic flow. We prove that every closed bounded k form, k≥2, on the universal covering of M is d(bounded). Further, if M is homotopy equivalent to a compact K?hler manifold, then its Euler number χ(M) satisfies (−1) ^m χ(M)>0. Received: 25 September 2001 / Published Online: 16 October 2002     

On the Graph Connectivity of Skeleta of Convex Polytopes

Given a d-dimensional convex polytope P and nonnegative integer k not exceeding d−1, let denote the simple graph on the node set of k-dimensional faces of P in which two such faces are adjacent if there exists a (k+1)-dimensional face of P which contains them both. The graph is isomorphic to the dual graph of the (d−k)-dimensional skeleton of the normal fan of P. For fixed values of k and d, the largest integer m such that is m-vertex-connected for all d-dimensional polytopes P is determined. This result generalizes Balinski’s theorem on the one-dimensional skeleton of a d-dimensional convex polytope. Supported by the 70/4/8755 ELKE Research Fund of the University of Athens.