Let $f\in \mathbb{R}[x_1,\ldots, x_k]$, for $k\ge 2$. For any finite sets $A_1,\ldots, A_k\subset \mathbb{R}$, consider the set $$ f(A_1,\ldots, A_k):=\{f(a_1,\ldots, a_k)\mid (a_1,\cdots,a_k)\in A_1\times\cdots \times A_k\}, $$ that is, the image of $A_1\times \cdots\times A_k$ under $f$. Extending a theorem of Elekes and Rónyai, which deals with the case $k=2$, and a result of Raz, Sharir, and De Zeeuw, dealing with the case $k=3$, it was proved Raz and Shem Tov, that for every choice of finite $A_1,\ldots, A_k\subset \mathbb{R}$, each of size $n$, one has \begin{equation}\label{RSbound} |f(A_1,\ldots,A_k)|=Ω(n^{3/2}), \end{equation} unless $f$ has some degenerate special form. In this paper, we introduce the notion of a {\it rank} of a $k$-variate polynomial $f$, denoted as ${\rm rank}(f)$. Letting $r={\rm rank}(f)$, we prove that \begin{equation} |f(A_1,\ldots,A_k)|=Ω\left(n^{\frac{5r-4}{2r}-\varepsilon}\right), \end{equation} for every $\varepsilon>0$, where the constant of proportionality depends on $\varepsilon$ and on ${\rm deg}(f)$. This improves the previous lower bound, for polynomials $f$ for which ${\rm rank}(f)\ge 3$. We present an application of our main result, to lower bound the number of distinct $d$-volumes spanned by $(d+1)$-tuples of points lying on the moment curve in $\mathbb{R}^d$.

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.

We extend the proximity technique of Solymosi and Zahl [J. Combin. Theory, Ser. A (2024)] to the setting of trivariate polynomials. In particular, we prove the following result: Let $f(x,y,z)=(x-y)^2+(φ(x)-z)^2$, where $φ(x)\in \mathbb{R}[x]$ has degree at least 3. Then, for every finite $A,B,C\subset \mathbb{R}$ each of size $n$, one has $|f(A,B,C)|=Ω(n^{5/3-\varepsilon})$, for every $\varepsilon>0$, where the constant of proportionality depends on $\varepsilon$ and on ${\rm deg}(φ)$. This improves the previous exponent $3/2$, due to Raz, Sharir, and De Zeeuw [Israel J. Math. (2018)]. To the best of our knowledge, prior to this work no trivariate polynomial was known to have expansion exceeding $Ω(n^{3/2})$.

Abstract. Let [Formula: see text] be a pair of constant-degree irreducible algebraic curves in [Formula: see text]. Assume that [Formula: see text] is contained in neither a hyperplane nor a quadric surface in [Formula: see text] for each [Formula: see text]. We show that for every pair of [Formula: see text]-point sets [Formula: see text] and [Formula: see text], the number of distinct distances spanned by [Formula: see text] is [Formula: see text] with a constant of proportionality that depends on [Formula: see text], [Formula: see text], and [Formula: see text]. This extends earlier results of Charalambides [ Discrete Comput. Geom., 51 (2014), pp. 666–701], Pach and de Zeeuw [ Combin. Probab. Comput., 26 (2017), pp. 99–117], and Raz [ Combin. Probab. Comput., 29 (2020), pp. 650–663] to the bipartite version. For the proof we use rigidity theory, and in particular the description of Bolker and Roth [ Pacific J. Math., 90 (1980), pp. 27–44] for realizations in [Formula: see text] of the complete bipartite graph [Formula: see text] that are not infinitesimally rigid.–

We show that the maximum number of pairwise nonoverlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $O(n^{3/2}\log(n / k^3)/k^{5/2} + n/k)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $O(n^{3/2}\log(n/k^3)/k^{3/2} + n)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). The second proof gives a bound that is weaker by a polylogarithmic factor. We then show that these bounds lead to the known bound of Agarwal et al. [ J. ACM, 51 (2004), pp. 139--186] and Marcus and Tardos [ J. Combin. Theory Ser. A, 113 (2006), pp. 675--691] on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.

We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.

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 L be a sequence (l_1,l_2,...,l_n) of n lines in C^3. We define the intersection graph G_L=([n],E) of L, where [n]:={1,..., n}, and with {i,j} in E if and only if i\neq j and the corresponding lines l_i and l_j intersect, or are parallel (or coincide). For a graph G=([n],E), we say that a sequence L is a realization of G if G subset G_L. One of the main results of this paper is to provide a combinatorial characterization of graphs G=([n],E) that have the following property: For every generic realization L of G, that consists of n pairwise distinct lines, we have G_L=K_n, in which case the lines of L are either all concurrent or all coplanar. The general statements that we obtain about lines, apart from their independent interest, turns out to be closely related to the notion of graph rigidity. The connection is established due to the so-called Elekes-Sharir framework, which allows us to transform the problem into an incidence problem involving lines in three dimensions. By exploiting the geometry of contacts between lines in 3D, we can obtain alternative, simpler, and more precise characterizations of the rigidity of graphs.

We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Omega(n^2), for any triple of lines (it is always O(n^2) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unit-area triangles.

Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.

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