Point sets with distinct distances

For positive integersd andn letf _d (n) denote the maximum cardinality of a subset of then ^d -gird {1,2,...,n} ^d with distinct mutual euclidean distances. Improving earlier results of Erds and Guy, it will be shown thatf ₂ (n)c·n ^2/3 and, ford3, thatf _d (n)c _d ·n ^2/3 ·(lnn)^1/3, wherec, c _d >0 are constants. Also improvements of lower bounds of Erds and Alon on the size of Sidon-sets in {1²,22²,...,n ²} are given.Furthermore, it will be proven that any set ofn points in the plane contains a subset with distinct mutual distances of sizec ₁·n ^1/4, and for point sets in genral position, i.e. no three points on a line, of sizec ₂·n ^1/3 with constantsc ₁,c ₂>0. To do so, it will be shown that forn points in ² with distinct distancesd ₁,d ₂,...,d _t , whered _i has multiplicitym _i , one has _i=1 ^t m _i ² c·n _3.25 for a positive constantc. If then points are in general position, then we prove _i=1 ^t m _i ² c·n ₃ for a positive constantc and this bound is tight.Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.     

On the number of antipodal or strictly antipodal pairs of points in finite subsets ofR d,II

The paper is a continuation of [MM], namely containing several statements related to the concept of antipodal and strictly antipodal pairs of points in a subsetX ofR ^d , which has cardinalityn. The pointsx _i, x_jX are called antipodal if each of them is contained in one of two different parallel supporting hyperplanes of the convex hull ofX. If such hyperplanes contain no further point ofX, thenx _i, x_j are even strictly antipodal. We shall prove some lower bounds on the number of strictly antipodal pairs for givend andn. Furthermore, this concept leads us to a statement on the quotient of the lengths of longest and shortest edges of speciald-simplices, and finally a generalization (concerning strictly antipodal segments) is proved.Research (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1817     

Some Erdös-Szekeres type results about points in space

The Erdös-Szekeres convexn-gon theorem states that for anyn3, there is a smallest integerf(n) such that any set of at leastf(n) points in the planeE ², no three collinear, contains the vertices of a convexn-gon. We consider three versions of this result as applied to convexly independent points and convex polytopes inE ^d >,d2.     

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.     

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.     

Approximation of convex bodies by simplices

This paper deals with the following kind of approximation of a convex bodyQ in Euclidean space E ⁿ by simplices: which is the smallest positive numberh _S(Q) such thatS ₁ Q S ₂ for a simplexS ₁ and its homothetic copyS ₂ of ratioh _S(Q). It is shown that ifS ₀ is a simplex of maximal volume contained inQ, then a homothetic copy ofS ₀ of ratio 13/3 containsQ.     

On averaging multisets

We give sufficient conditions to ensure that, given a set , everyxint convM can be represented as a convex combination,x = _{i = 1} ⁿ _i x _i , wherex _i M, _i rational, andn=2s orn=2s–1, respectively.     

On neighborly families of convex bodies

A family of convex bodies in E^d is called neighborly if the intersection of every two of them is (d-1)-dimensional. In the present paper we prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d, d 3, such that every two of them are affinely equivalent (i.e., there is an affine transformation mapping one of them onto another), the bodies have large groups of affine automorphisms, and the volumes of the bodies are prescribed. We also prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d such that the bodies have large groups of symmetries. These two results are answers to a problem of B. Grünbaum (1963). We prove also that there exist arbitrarily large neighborly families of similar convex d-polytopes in E^d with prescribed diameters and with arbitrarily large groups of symmetries of the polytopes.     

The combinatorial structure of random polytopes

Choose n random points in , let P_n be their convex hull, and denote by f_i(P_n) the number of i-dimensional faces of P_n. A general method for computing the expectation of f_i(P_n), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for f_i(P_n) is proved as n→∞. For random points chosen in a polytope the expectation of f_i(P_n) is determined as n→∞. This implies an extremal property for random points chosen in a simplex.     

The maximal monotonicity of the subdifferentials of convex functions: Simons' problem

In the paper we deal with the problem when the graph of the subdifferential operator of a convex lower semicontinuous function has a common point with the product of two convex nonempty weak and weak^* compact sets, i.e. when graph (Q × Q ^*) 0. The results obtained partially solve the problem posed by Simons as well as generalize the Rockafellar Maximal Monotonicity Theorem.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

Isoperimetric inequalities in potential theory

Given a non-empty bounded domainG in ⁿ ,n2, letr ₀(G) denote the radius of the ballG ₀ having center 0 and the same volume asG. The exterior deficiencyd _e (G) is defined byd _e (G)=r _e (G)/r ₀(G)–1 wherer _e (G) denotes the circumradius ofG. Similarlyd _i (G)=1–r _i (G)/r ₀(G) wherer _i (G) is the inradius ofG. Various isoperimetric inequalities for the capacity and the first eigenvalue ofG are shown. The main results are of the form CapG(1+cf(d _e (G)))CapG ₀ and ₁(G)(1+cf(d _i (G)))₁(G ₀),f(t)=t ³ ifn=2,f(t)=t ³/(ln 1/t) ifn=3,f(t)=t ^(n+3)/2 ifn4 (for convex G and small deficiencies ifn3).     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

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

The cross-section body, plane sections of convex bodies and approximation of convex bodies, I

For a convex body K ^d we investigate three associated bodies, its intersection body IK (for 0int K), cross-section body CK, and projection body IIK, which satisfy IKCKIIK. Conversely we prove CKconst₁(d)I(K–x) for some xint K, and IIKconst₂ (d)CK, for certain constants, the first constant being sharp. We estimate the maximal k-volume of sections of 1/2(K+(-K)) with k-planes parallel to a fixed k-plane by the analogous quantity for K; our inequality is, if only k is fixed, sharp. For L ^d a convex body, we take n random segments in L, and consider their Minkowski average D. We prove that, for V(L) fixed, the supremum of V(D) (with also nN arbitrary) is minimal for L an ellipsoid. This result implies the Petty projection inequality about max V((IIM)*), for M ^d a convex body, with V(M) fixed. We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, the volumes of sections of convex bodies and the volumes of sections of their circumscribed cylinders. For fixed n, the pth moments of V(D) (1p<) also are minimized, for V(L) fixed, by the ellipsoids. For k=2, the supremum (nN arbitrary) and the pth moment (n fixed) of V(D) are maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 41.     

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.     

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     

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.     

Sets determined by finitely many X-rays

A measurable set in _n which is uniquely determined among all measurable sets (modulo null sets) by its X-rays in a finite set L of directions, or more generally by its X-rays parallel to a finite set L of subspaces, is called L-unique, or simply unique. Some subclasses of the L-unique sets are known. The L-additive sets are those measurable sets E which can be written E {x _n : _i f _i (x) * 0}. Here, denotes equality modulo null sets, * is either or >, and the terms in the sum are the values of ridge functions f _i orthogonal to subspaces S _i in L. If n=2, the L-inscribable convex sets are those whose interiors are the union of interiors of inscribed convex polygons, all of whose sides are parallel to the lines in L. Relations between these classes are investigated. It is shown that in _n each L-inscribable convex set is L-additive, but L-additive convex sets need not be L-inscribable. It is also shown that every ellipsoid in _n is unique for any set of three directions. Finally, some results are proved concerning the structure of convex sets in _n , unique with respect to certain families of coordinate subspaces.     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000