According to a classical result of Spencer, Szemerédi, and Trotter (1984), the maximum number of times the unit distance can occur among n points in the plane is O(n^{4/3}). This is far from Erdős’s lower bound, n^{1+O(1/log log n)}, which is conjectured to be optimal. We prove a structural result for point sets with nearly n^{4/3} unit distances and use it to reduce the problem to a conjecture on rigid frameworks. This conjecture, if true, would yield the first improvement on the bound of Spencer et al. A weaker version of this conjecture has been established by Raz and Solymosi.

Abstract. In the 60s, Micha Perles constructed a point-line arrangement in the plane on nine points, which can not be realized only by points with rational coordinates. Grünbaum conjectured that Perles’ construction is the smallest: any geometric arrangement on eight or fewer points, if it is realizable with real coordinates in the plane, it is also realizable with rational coordinates. In this note, we prove the conjecture.

In this paper we show examples for applications of the Bombieri--Lang conjecture in additive combinatorics, giving bounds on the cardinality of sumsets of squares and higher powers of integers.

While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper. We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.

Let p1, p2, p3 be three distinct points in the plane, and, for i = 1, 2, 3, let Ci be a family of n unit circles that pass through pi. We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is O(n11/6), improving an earlier bound for this problem due to Elekes, Simonovits, and Szabó [4]. The problem is a special instance of a more general problem studied by Elekes and Szabó [5] (and by Elekes and Rónyai [3]).

In this paper we characterize real bivariate polynomials which have a small range over large Cartesian products. We show that for every constant-degree bivariate real polynomial f, either |f(A, B)| = Ω(n4/3), for every pair of finite sets A, B ⊂ R, with |A| = |B| = n (where the constant of proportionality depends on deg f), or else f must be of one of the special forms f(u, v) = h(φ(u) + ψ(v)), or f(u, v) = h(φ(u) · ψ(v)), for some univariate polynomials φ, ψ, h over R. This significantly improves a result of Elekes and Rónyai [7].

We present some elementary ideas to prove the following Sylvester–Gallai type theorems involving incidences between points and lines in the planes over the complex numbers and quaternions. 1. Let A and B be finite sets of at least two complex numbers each. Then there exists a line $\ell$ in the complex affine plane such that $\lvert(A\times B)\cap\ell\rvert=2$. 2. Let S be a finite noncollinear set of points in the complex affine plane. Then there exists a line $\ell$ such that $2\leq \lvert S\cap\ell\rvert \leq 5$. 3. Let A and B be finite sets of at least two quaternions each. Then there exists a line $\ell$ in the quaternionic affine plane such that $2\leq \lvert(A\times B)\cap\ell\rvert \leq 5$. 4. Let S be a finite noncollinear set of points in the quaternionic affine plane. Then there exists a line $\ell$ such that $2\leq \lvert S\cap\ell\rvert \leq 24$.

Given a finite set of complex numbers A we say that a transformation on the complex numbers, T: C → C is k-rich on A if |A ∩ T(A)|≥ k. In this paper we give a bounds on the number of k-rich linear and Mobius transformations for any given set A. Our results have applications to discrete geometry and to additive combinatorics.

The Szemerédi–Trotter theorem [Combinatorica, 3 (1983), pp. 381–392] gives a bound on the maximum number of incidences between points and lines on the Euclidean plane. In particular it says that n lines and n points determine $O(n^{4/3})$ incidences. Let us suppose that an arrangement of n lines and n points defines $cn^{4/3}$ incidences, for a given positive c. It is widely believed that such arrangements have special structure, but no results are known in this direction. Here we show that for any natural number, k, one can find k points of the arrangement in general position such that any pair of them is incident to a line from the arrangement, provided by $n\geq n_0(k)$. In a subsequent paper we will establish a similar statement for hyperplanes.

We show that the number of distinct distances in a well-distributed set of n points in Rd is O (n2/d-1/d2) which is not far from the best known upper bound O(n2/d).

It is shown that every set of $n$ points in the plane has an element f rom which there are at least $cn^{6/7}$ other elements at distinct distances, where $c>0$ is a constant. This improves earlier results of Erd\H os, Moser, Beck, Chung, Szemer\'edi, Trotter, and Sz\'ekely.

We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the Random-Edge simplex algorithm on simple polytopes with n facets in dimension n-2. We obtain a tight O(\log^2 n) bound for the expected number of pivot steps. This is the first nontrivial bound for Random-Edge which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2-variable linear programming problems, and we prove a tight t(n) bound for its expected runtime.The combinatorial structure behind the process is a directed graph over pairs of points, with arc orientations induced by the pivot steps. We characterize the class of graphs arising from one line and n points, up to oriented matroid realizability.