On distinct distances among points in general position and other related problems

A set of points in the plane is said to be in general position if no three of them are collinear and no four of them are cocircular. If a point set determines only distinct vectors, it is called parallelogram free. We show that there exist n-element point sets in the plane in general position, and parallelogram free, that determine only O(n ²/√log n) distinct distances. This answers a question of Erd?s, Hickerson and Pach. We then revisit an old problem of Erd?s: given any n points in the plane (or in d dimensions), how many of them can one select so that the distances which are determined are all distinct? — and provide (make explicit) some new bounds in one and two dimensions. Other related distance problems are also discussed.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

Maximal sets of permutations constructed from projective planes

On the set of n²+n+1 points of a projective plane, a set of n²+n+1 permutations is constructed with the property that any two are a Hamming distance 2n+1 apart. Another set is constructed in which every pair are a Hamming distance not greater than 2n+1 apart. Both sets are maximal with respect to the stated property.     

General decomposition theorems form-convex sets in the plane

A setS inR ^dis said to bem-convex,m≧2, if and only if for everym distinct points inS, at least one of the line segments determined by these points lies inS. Clearly any union ofm?1 convex sets ism-convex, yet the converse is false and has inspired some interesting mathematical questions: Under what conditions will anm-convex set be decomposable intom?1 convex sets? And for everym≧2, does there exist aσ(m) such that everym-convex set is a union ofσ(m) convex sets? Pathological examples convince the reader to restrict his attention to closed sets of dimension≦3, and this paper provides answers to the questions above for closed subsets of the plane. IfS is a closedm-convex set in the plane,m ≧ 2, the first question may be answered in one way by the following result: If there is some lineH supportingS at a pointp in the kernel ofS, thenS is a union ofm ? 1 convex sets. Using this result, it is possible to prove several decomposition theorems forS under varying conditions. Finally, an answer to the second question is given: Ifm≧3, thenS is a union of (m?1)³2 ^m?3 or fewer convex sets.     

Reconstructing Geometric Objects from the Measures of Their Intersections with Test Sets

Let us say that an element of a given family $\mathcal{A}$ of subsets of ? ^d can be reconstructed using n test sets if there exist T ₁,…,T _n ?? ^d such that whenever $A,B\in\mathcal{A}$ and the Lebesgue measures of A∩T _i and B∩T _i agree for each i=1,…,n then A=B. Our goal will be to find the least such n. We prove that if $\mathcal{A}$ consists of the translates of a fixed reasonably nice subset of ? ^d then this minimum is n=d. To obtain this we prove the following two results. (1) A translate of a fixed absolutely continuous function of one variable can be reconstructed using one test set. (2) Under rather mild conditions the Radon transform of the characteristic function of K (that is, the measure function of the sections of K), (R _θ χ _K )(r)=λ ^d?1(K∩{x∈? ^d :〈x,θ〉=r}) is absolutely continuous for almost every direction θ. These proofs are based on techniques of harmonic analysis. We also show that if $\mathcal{A}$ consists of the enlarged homothetic copies rE+t (r≥1,t∈? ^d ) of a fixed reasonably nice set E?? ^d , where d≥2, then d+1 test sets reconstruct an element of $\mathcal{A}$ , and this is optimal. This fails in ?: we prove that a closed interval, and even a closed interval of length at least 1 cannot be reconstructed using two test sets. Finally, using randomly constructed test sets, we prove that an element of a reasonably nice k-dimensional family of geometric objects can be reconstructed using 2k+1 test sets. An example from algebraic topology shows that 2k+1 is sharp in general.     

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

Long paths and cycles in subgraphs of the cube

Let Q _n denote the graph of the n-dimensional cube with vertex set {0, 1} ⁿ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose G is a subgraph of Q _n with average degree at least d. How long a path can we guarantee to find in G? Our aim in this paper is to show that G must contain an exponentially long path. In fact, we show that if G has minimum degree at least d then G must contain a path of length 2 ^d ? 1. Note that this bound is tight, as shown by a d-dimensional subcube of Q _n . We also obtain the slightly stronger result that G must contain a cycle of length at least 2 ^d .     

Chebyshev Polynomials on Compact Sets

In connection with a problem of H. Widom it is shown that if a compact set K on the complex plane contains a smooth Jordan arc on its outer boundary, then the minimal norm of monic polynomials of degree n?=?1,2,... is at least (1?+?β)cap(K) ⁿ with some β?>?0, where cap(K) ⁿ would be the theoretical lower bound. It is also shown that the rate (1?+?o(1))cap(K) ⁿ is possible only for compact for which the unbounded component of the complement is simply connected. A related result for sets lying on the real line is also proven.     

Approximation of the limit distance function in Banach spaces

In this paper we study the behavior of the limit distance function d(x)=limdist(x,Cn) defined by a nested sequence (Cn) of subsets of a real Banach space X. We first present some new criteria for the non-emptiness of the intersection of a nested sequence of sets and of their ε-neighborhoods from which we derive, among other results, Dilworth's characterization [S.J. Dilworth, Intersections of centred sets in normed spaces, Far East J. Math. Sci. (Part II) (1988) 129-136 (special volume)] of Banach spaces not containing c₀ and Marino's result [G. Marino, A remark on intersection of convex sets, J. Math. Anal. Appl. 284 (2003) 775-778]. Passing then to the approximation of the limit distance function, we show three types of results: (i) that the limit distance function defined by a nested sequence of non-empty bounded closed convex sets coincides with the distance function to the intersection of the weak^∗-closures in the bidual; this extends and improves the results in [J.M.F. Castillo, P.L. Papini, Distance types in Banach spaces, Set-Valued Anal. 7 (1999) 101-115]; (ii) that the convexity condition is necessary; and (iii) that in spaces with separable dual, the distance function to a weak^∗-compact convex set is approximable by a (non-necessarily nested) sequence of bounded closed convex sets of the space.     

On space coverings by unbounded convex sets

Let (C_i) be a sequence of closed convex subsets of Euclidean n-space Eⁿ. This paper is concerned with the problem of finding necessary and sufficient conditions that the sets C_i can be rearranged (by the application of rigid motions or translations) so as to cover all or almost all Eⁿ. Particular attention is paid to the problems that arise if the sets C_i are permitted to be unbounded. It is shown that under certain conditions this covering problem can be reduced to the already thoroughly investigated case of compact sets with bounded diameter set{d(C_i)}, and it is also proved that there are two additional covering possibilities if such a reduction is not possible.     

The extension of the D(?k 2)-pair {k 2,k 2 + 1}

Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k ², k ²+1, c, d} is a D(?k ²)-quadruple with c < d, then c = 1 and d = 4k ²+1. This extends the work of the first author [20] and that of Dujella [4].     

Random matrix models of stochastic integral type for free infinitely divisible distributions

The Bercovici-Pata bijection maps the set of classical infinitely divisible distributions to the set of free infinitely divisible distributions. The purpose of this work is to study random matrix models for free infinitely divisible distributions under this bijection. First, we find a specific form of the polar decomposition for the Lévy measures of the random matrix models considered in Benaych-Georges [6] who introduced the models through their laws. Second, random matrix models for free infinitely divisible distributions are built consisting of infinitely divisible matrix stochastic integrals whenever their corresponding classical infinitely divisible distributions admit stochastic integral representations. These random matrix models are realizations of random matrices given by stochastic integrals with respect to matrix-valued Lévy processes. Examples of these random matrix models for several classes of free infinitely divisible distributions are given. In particular, it is shown that any free selfdecomposable infinitely divisible distribution has a random matrix model of Ornstein-Uhlenbeck type ?? ₀ ^?? e ^?1 d?? _t ^d , d ?? 1, where ?? _t ^d is a d × d matrix-valued Lévy process satisfying an I _log condition.     

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

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

On the index sets of Σ-subsets of the real numbers

We compute the levels of complexity in analytical and arithmetical hierarchies for the sets of the Σ-formulas defining in the hereditarily finite superstructure over the ordered field of the reals the classes of open, closed, clopen, nowhere dense, dense subsets of ? ⁿ , first category subsets in ? ⁿ as well as the sets of pairs of Σ-formulas corresponding to the relations of set equality and inclusion which are defined by them. It is also shown that the complexity of the set of the Σ-formulas defining connected sets is at least Π ₁ ¹ .     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

A Planar 3-Convex Set is Indeed a Union of Six Convex Sets

Suppose S is a planar set. Two points $a,b$ in S  see each other via S if $[a,b]$ is included in S . F. Valentine proved in 1957 that if S is closed, and if for every three points of S, at least two see each other via S, then S is a union of three convex sets. The pentagonal star shows that the number three is the best possible. We drop the condition that S is closed and show that S is a union of (at most) six convex sets. The number six is best possible.     

Coding with injections

A permutation code of length n and minimum distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between any distinct ${u,v \in \Gamma}$ is at least d. As a generalization, we introduce the problem of packing injections from an m-set, m ≤?n, sometimes called m-arrangements, relative to Hamming distance. We offer some preliminary coding-theoretic bounds, a few design-theoretic connections, and a short discussion on possible applications.     

Properties of P-sets and trapped compact convex sets

New properties of P-sets, which constitute a large class of convex compact sets in ? ⁿ that contains all convex polyhedra and strictly convex compact sets, are obtained. It is shown that the intersection of a P-set with an affine subspace is continuous in the Hausdorff metric. In this theorem, no assumption of interior nonemptiness is made, unlike in other known intersection continuity theorems for set-valued maps. It is also shown that if the graph of a set-valued map is a P-set, then this map is continuous on its entire effective set rather than only on the interior of this set. Properties of the so-called trapped sets are also studied; well-known Jung’s theorem on the existence of a minimal ball containing a given compact set in ? ⁿ is generalized. As is known, any compact set contains n + 1 (or fewer) points such that any translation by a nonzero vector takes at least one of them outside the minimal ball. This means that any compact set is trapped in the minimal ball. Compact sets trapped in any convex compact sets, rather than only in norm bodies, are considered. It is shown that, for any compact set A trapped in a P-set M ? ? ⁿ , there exists a set A ⁰ ? A trapped in M and containing at most 2n elements. An example of a convex compact set M ? ? ⁿ for which such a finite set A ⁰ ? A does not exist is given.     

A closed (n + 1)-convex set inR 2 is a union ofn 6 convex sets

It is shown that if a closed setS in the plane is (n+1)-convex, then it has no more thann ⁴ holes. As a consequence, it can be covered by≤n ⁶ convex subsets. This is an improvement on the known bound of 2 ⁿ ·n ³. The author would like to thank the BSF for partially supporting this research. Publication no. 354.