Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

i-perfectm-cycle systems,m ≤ 19

Summary For allm 19 and each meaningful value ofi (2 i m/2), the spectrum problem fori-perfectm-cycle systems is examined.     

Integrability of certain solutions of differential equations

Let L=P_o(d/d_t)ⁿ+P₁(d/d_t)^n–1+...+P_n denote a formally self-adjoint differential expression on an open intervalI=(a, b) (–a. Here the P_k are complex valued with (n — k) continuous derivatives onI, and P₀(t) 0 onI. We discuss integrability of functions which are adjoint to certain fundamental solutions ofLy=y, and a related consequence.     

Variations on the theme of repeated distances

We give an asymptotically sharp estimate for the error term of the maximum number of unit distances determined byn points in ^{d, d}4. We also give asymptotically tight upper bounds on the total number of occurrences of the favourite distances fromn points in ^{d, d}4. Related results are proved for distances determined byn disjoint compact convex sets in ².At the time this paper was written, both authors were visiting the Technion — Israel Institute of Technology.     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

On the problem of two linearized wells

We study the behaviour of sequences of elastic deformationsy ^{n n} whose gradients approach two linearized wells, and give an application to magnetostriction.This article was processed by the author using the style filepljour1m from Springer-Verlag.     

Designs and partial geometries over finite fields

Let be a finite field, and let (, B) be a nontrivial 2-(n, k, 1)-design over . Then each point induces a (k–1)-spread S on /. (, B) is said to be a geometric design if S is a geometric spread on / for each . In this paper, we prove that there are no geometric designs over any finite field .Research partially supported by NSF grant DMS-8703229.     

The Resolution Method for One Reducible Class of Formulas of the First-Order Modal Logic S4

In the paper, we describe a resolution method for the family of the formulas of the form *ⁱ**(L ₁ L _s ), where i = 0 1 and L _j are modal literals. Negations here stand directly before classical atomic formulas, the formulas may contain constants. We also present the absorption tactics for a set of such formulas.__________Translated from Lietuvos Matematikos Rinkinys, Vol. 44, No. 4, pp. 481–492, October–December, 2004.     

Estimates for the minimal width of polytopes inscribed in convex bodies

The paper deals with the problem of approximating point sets byn-point subsets with respect to the minimal widthw. Let, in particular, ^d denote the family of all convex bodies in Euclideand-space, letA ^d and letn be an integer greater thand. Then we ask for the greatest number = _n (A) such that everyA A contains a polytope withn vertices which has minimal width at least w(A). We give bounds for _n ( ^d ), for _n (2133; ^d ), and for _n (W ^d ), where 2133; ^d ,W ^d denote the families of centrally symmetric convex bodies and of bodies of constant width, respectively.Dedicated to Professor L. danzer on the occasion of his sixtieth birthdayResearch for this paper was conducted in the academic year 1986/87 while both authors were visiting the University of Washington, Seattle. P. Gritzmann was supported by the Alexander von Humboldt Foundation.     

The hypermetric cone is polyhedral

The hypermetric coneH _n is the cone in the spaceR ^n(n–1)/2 of all vectorsd=(d _ij)_1i<jn satisfying the hypermetric inequalities: –_1ijn z _j z _j d _ij 0 for all integer vectorsz inZ ⁿ with –_1in z _i =1. We explore connections of the hypermetric cone with quadratic forms and the geometry of numbers (empty spheres andL-polytopes in lattices). As an application, we show that the hypermetric coneH _n is polyhedral.     

Geometric methods in the study of irregularities of distribution

Let be a signed measure on E ^d with E ^d =0 and ¦¦E^d<. DefineD _s() as sup ¦H¦ whereH is an open halfspace. Using integral and metric geometric techniques results are proved which imply theorems such as the following.Theorem A. Let be supported by a finite pointsetp _i. ThenD _s()>c _d(₁/ ₂)^1/2{ _{i(p i})²}^1/2 where ₁ is the minimum distance between two distinctp _i, and ₂ is the maximum distance. The numberc _d is an absolute dimensional constant. (The number .05 can be chosen forc ₂ in Theorem A.)Theorem B. LetD be a disk of unit area in the planeE ², andp ₁,p ₂,...,p _n be a set of points lying inD. If m if the usual area measure restricted toD, while nP _i=1/n defines an atomic measure _n, then independently of _n,nD _s(m – _n) .0335n ^1/4. Theorem B gives an improved solution to the Roth disk segment problem as described by Beck and Chen. Recent work by Beck shows thatnD _s(m – _n)cn ^1/4(logn)^–7/2.     

Sum of sets in several dimensions

LetA, B be finite sets in ^d with|A|=m|B|=n, and assume that there is no hyperplane containing both a translation ofA and a translation ofB. Under this condition it is proved that the number of distinct vectors in the form {a+baA, bB} is at leastn+dm–d(d+1)/2. This generalizes results of Freiman (caseA=B) and Freiman, Heppes, Uhrin (caseA=–B). A more complicated estimate is also given which yields the exact bound for alln>2d.Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901.     

On representing contexts in line arrangements

Acontext is defined to be a triple (G, M, J) of setsG, M and an incidence relationJ G×M.A finite set ofn oriented lines in general position in the euclidean plane induces a cell decomposition of the plane. For a givenk-element subset of cells of dimension 2, we define an incidence relationJ × as follows:t _i andl _j are incident if and only ift _i lies on the positive side with respect tol _j .We call a context (G, M, J)represented in a line arrangement if and only if there are relation preserving bijections betweenG and ,M and , respectively. We study conditions for a context to be representable in a line arrangement.Especially, we provide a non-trivial infinite class of contexts which can not be represented in a line arrangement.     

Extensions of an inequality of Bonnesen toD-dimensional space and curvature conditions for convex bodies

For convex bodies inE ^d (d 3) with diameter 2 we consider inequalitiesW _i – W _d–1 +( - 1) W _d 0 (i = 0, , d – 2) whereW _j are the quermassintegrals. In addition, for a ball, equality is attained for a body of revolution for which the elementary symmetric functions _d–1–i of main curvature radii is constant. The inequality is actually proved fori = d – 2 by means of Weierstrass's fundamental theorem of the calculus of variations.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Cyclic Just-In-Time Sequences Are Optimal

Consider the Product Rate Variation problem. Given n products 1,...,i,...,n, and n positive integer demands d ₁,..., d_i,...,d_n. Find a sequence =₁,...,_T, T = _i=1 ⁿ d _i, of the products, where product i occurs exactly d _i times that always keeps the actual production level, equal the number of product i occurrences in the prefix ₁,..., _t, t=1,...,T, and the desired production level, equal r _i t, where r _i=d_i/T, of each product i as close to each other as possible. The problem is one of the most fundamental problems in sequencing flexible just-in-time production systems. We show that if is an optimal sequence for d ₁,...,d_i,...,d_n, then concatenation ^m of m copies of is an optimal sequence for md ₁,..., md_i,...,md_n.     

A sandwich theorem and Hyers—Ulam stability of affine functions

It is shown that two real functionsf andg, defined on a real intervalI, satisfy the inequalitiesf(x + (1 – )y) g(x) + (1 – )g(y) andg(x + (1 – )y) f(x) + (1 – )f(y) for allx, y I and [0, 1], iff there exists an affine functionh: I such thatf h g. As a consequence we obtain a stability result of Hyers—Ulam type for affine functions.     

Note dual polytopes of rational convex polytopes

LetP ^d be a rational convex polytope with dimP=d such that the origin of ^d is contained in the interiorP – P ofP. In this paper, from a viewpoint of enumeration of certain rational points inP (which originated in Ehrhart's work), a necessary and sufficient condition for the dual polytopeP ^dual ofP to be integral is presented.This research was performed while the author was staying at Massachusetts Institute of Technology during the 1988–89 academic year.     

On the Sobolev distance of convex bodies

Summary LetK ^d denote the cone of all convex bodies in the Euclidean spaceK ^d . The mappingK h _K of each bodyK K ^d onto its support function induces a metric _w onK ^d by" _w (K, L)h _L –h _{K w} where _w is the Sobolev I-norm on the unit sphere . We call _w (K, L) the Sobolev distance ofK andL. The goal of our paper is to develop some fundamental properties of the Sobolev distance.     

Über nullstellenfreie Gebiete von ζ(itk) (s)

Let ^(itk) (s) denote thek-th derivative of the Riemann Zeta-function,s=+it, ,t real numbers,k1 rational integers. Using ideas fromT. C. Titchmarsh and from a paper ofR. Spira, lower bounds are derived for |^(itk)(s)|, |^(itk)(1-s) for >1 and some infinitely many, sufficiently large values oft. Further let be an algebraic number of degreen and heightH; then a lower bound for |^(itk)(its)|, dependent onn, H, k is established for alln,H1,k3, 2+7k/4 and all realt.