On distinct sums and distinct distances

The paper (Discrete Comput. Geom. 25 (2001) 629) of Solymosi and Tóth implicitly raised the following arithmetic problem. Consider n pairwise disjoint s element sets and form all sums of pairs of elements of the same set. What is the minimum number of distinct sums one can get this way? This paper proves that the number of distinct sums is at least n^d_s, where d_s=1/c_⌈s/2⌉ is defined in the paper and tends to e⁻¹ as s goes to infinity. Here e is the base of the natural logarithm. As an application we improve the Solymosi-Tóth bound on an old Erdős problem: we prove that n distinct points in the plane determine distinct distances, where ε>0 is arbitrary. Our bound also finds applications in other related results in discrete geometry. Our bounds are proven through an involved calculation of entropies of several random variables.     

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.     

k-Moments of distances between centers of Ford circles

In this paper, we investigate a problem on the distribution of Ford circles, which concerns moments of distances between centers of these circles that lie above a given horizontal line.     

Three distinct distances in the plane

For n6 all sets of n points in the plane with three distinct distances are determined.Dedicated to Professor Dr. Laszlo Fejes Töth on the occasion of his eightieth birthday     

Diffeomorphisms taking lines to circles, and quaternionic Hopf fibrations

We list all diffeomorphisms between an open subset of the four-dimensional projective space and an open subset of the four-dimensional sphere that take all line segments to arcs of round circles. These diffeomorphisms are restrictions of quaternionic Hopf fibrations and radial projections from hyperplanes to spheres.     

Ring domains with separating circles or separating annuli

Partially supported by the University of Cincinnati's Summer Faculty Research Program.     

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 surfaces inP 6 with no trisecant lines

Examples of surfaces inP ⁶ with no trisecant lines are constructed. A partial classification recovering them is given and conjectured to be the complete one. Dedicated to the memory of F. Serrano     

On extremal weighted digraphs with no heavy paths

Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.     

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

On the sum of all distances in a graph or digraph

The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2-connected or 2-edge-connected graphs of order n, the maximal transmission is realized only by the cycle C_n. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP-hardness of some related algorithmic problems.     

Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.     

Finite groups in which no two distinct conjugacy classes have the same order

Archiv der Mathematik -     

Random polynomials having few or no real zeros

Consider a polynomial of large degree whose coefficients are independent, identically distributed, nondegenerate random variables having zero mean and finite moments of all orders. We show that such a polynomial has exactly real zeros with probability as through integers of the same parity as the fixed integer . In particular, the probability that a random polynomial of large even degree has no real zeros is . The finite, positive constant is characterized via the centered, stationary Gaussian process of correlation function . The value of depends neither on nor upon the specific law of the coefficients. Under an extra smoothness assumption about the law of the coefficients, with probability one may specify also the approximate locations of the zeros on the real line. The constant is replaced by in case the i.i.d. coefficients have a nonzero mean.

     

On reconstructing n-point configurations from the distribution of distances or areas

One way to characterize configurations of points up to congruence is by considering the distribution of all mutual distances between points. This paper deals with the question if point configurations are uniquely determined by this distribution. After giving some counterexamples, we prove that this is the case for the vast majority of configurations.In the second part of the paper, the distribution of areas of sub-triangles is used for characterizing point configurations. Again it turns out that most configurations are reconstructible from the distribution of areas, though there are counterexamples.