Explore the vast range of titles available.

We show that, for a constant-degree algebraic curve γ in ℝD, every set of n points on γ spans at least Ω(n4/3) distinct distances, unless γ is an algebraic helix, in the sense of Charalambides [2]. This improves the earlier bound Ω(n5/4) of Charalambides [2]. We also show that, for every set P of n points that lie on a d-dimensional constant-degree algebraic variety V in ℝD, there exists a subset S ⊂ P of size at least Ω(n4/(9+12(d−1))), such that S spans $\\left({\\begin{array}{*{20}{c}} {|S|} \\\ 2 \\\\\end{array}} \\right)$ distinct distances. This improves the earlier bound of Ω(n1/(3d)) of Conlon, Fox, Gasarch, Harris, Ulrich and Zbarsky [4]. Both results are consequences of a common technical tool.

While the problem of determining whether an embedding of a graph G in R2 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 C0n3/2(logn)β edges, for some absolute constants C0>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. 58(4), 986–1009 (2017)), between the notion of graph rigidity and configurations of lines in R3. This connection allows us to use properties of line configurations established in Guth and Katz (Ann. Math. 181(1), 155–190 (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 Ω(n3/2logn) is tight, and we provide a construction that shows that requiring Ω(nlogn) edges is necessary.

The d -dimensional algebraic connectivity a d ( G ) of a graph G = ( V,E ), introduced by Jordán and Tanigawa, is a quantitative measure of the d -dimensional rigidity of G that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set V into ℝ d . Here, we analyze the d -dimensional algebraic connectivity of complete graphs. In particular, we show that, for d ≥ 3, a d ( K d +1 ) = 1, and for n ≥ 2 d , ⌈ n 2 d ⌉ − 2 d + 1 ≤ a d ( K n ) ≤ 2 n 3 ( d − 1 ) + 1 3 .

Let L be a sequence ( ℓ 1 , ℓ 2 , … , ℓ 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 } ∈ E if and only if i ≠ j and the corresponding lines ℓ i and ℓ 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 ⊂ 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 (see Definition  4.1 ) 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.

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 ⊂ ℝ, 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 ℝ. This significantly improves a result of Elekes and Rónyai (2000). Our results are cast in a more general form, in which we give an upper bound for the number of zeros of z = f(x,y) on a triple Cartesian product A × B × C, when the sizes |A|, |B|, |C| need not be the same; the upper bound is O(n11/6) when |A| = |B| = |C| = n, where the constant of proportionality depends on deg f, unless f has one of the aforementioned special forms. This result provides a unified tool for improving bounds in various Erdős-type problems in geometry and additive combinatorics. Several applications of our results to problems of these kinds are presented. For example, we show that the number of distinct distances between n points lying on a constant-degree algebraic curve that has a polynomial parameterization, and that does not contain a line, in any dimension, is Ω(n4/3), extending the result of Pach and de Zeeuw (2014) and improving the bound of Charalambides (2014), for the special case where the curve under consideration has a polynomial parameterization. We also derive improved lower bounds for several variants of the sum-product problem in additive combinatorics.

Let p 1 , p 2 , p 3 be three distinct points in the plane, and, for i = 1 , 2 , 3 , let C i be a family of n unit circles that pass through p i . We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is O ( n 11 / 6 ) , improving an earlier bound for this problem due to Elekes et al. (Comb Probab Comput 18:691–705, 2009 ). The problem is a special instance of a more general problem studied by Elekes and Szabó (Combinatorica 32:537–571, 2012 ) [and by Elekes and Rónyai (J Comb Theory Ser A 89:1–20, 2000 )].

We define a generic rigidity matroid for k-volumes of a simplicial complex in $\\mathbb {R}^d$ and prove that for $2\\leq k \\leq d-1$ it has the same rank as the classical generic d-rigidity matroid on the same vertex set (namely, the case $k=1$ ). This is in contrast with the $k=d$ case, previously studied by Lubetzky and Peled, which presents a different behavior. We conjecture a characterization for the bases of this matroid in terms of d-rigidity of the $1$ -skeleton of the complex and a combinatorial Hall condition on incidences of edges in k-faces.

We consider four related problems. (1) Obtaining dimension estimates for the set of exceptional vantage points for the pinned Falconer distance problem. (2) Nonlinear projection theorems, in the spirit of Kaufman, Bourgain, and Shmerkin. (3) The parallelizability of planar \\(d\\)-webs. (4) The Elekes-Rónyai theorem on expanding polynomials. Given a Borel set \\(A\\) in the plane, we study the set of exceptional vantage points, for which the pinned distance \\(\\Delta_p(A)\\) has small dimension, that is, close to \\((\\dim A)/2\\). We show that if this set has positive dimension, then it must have very special structure. This result follows from a more general single-scale nonlinear projection theorem, which says that if \\(\\phi_1,\\phi_2,\\phi_3\\) are three smooth functions whose associated 3-web has non-vanishing Blaschke curvature, and if \\(A\\) is a \\((\\delta,\\alpha)_2\\)-set in the sense of Katz and Tao, then at least one of the images \\(\\phi_i(A)\\) must have measure much larger than \\(|A|^{1/2}\\), where \\(|A|\\) stands for the measure of \\(A\\). We prove analogous results for \\(d\\) smooth functions \\(\\phi_1,\\ldots,\\phi_d\\), whose associated \\(d\\)-web is not parallelizable. We use similar tools to characterize when bivariate real analytic functions are \"dimension expanding\" when applied to a Cartesian product: if \\(P\\) is a bivariate real analytic function, then \\(P\\) is either locally of the form \\(h(a(x) + b(y))\\), or \\(P(A,B)\\) has dimension at least \\(\\alpha+c\\) whenever \\(A\\) and \\(B\\) are Borel sets with Hausdorff dimension \\(\\alpha\\). Again, this follows from a single-scale estimate, which is an analogue of the Elekes-Rónyai theorem in the setting of the Katz-Tao discretized ring conjecture.

We show that, for a constant-degree algebraic curve \\(\\gamma\\) in \\(\\mathbb{R}^D\\), every set of \\(n\\) points on \\(\\gamma\\) spans at least \\(\\Omega(n^{4/3})\\) distinct distances, unless \\(\\gamma\\) is an {\\it algebraic helix} (see Definition 1.1). This improves the earlier bound \\(\\Omega(n^{5/4})\\) of Charalambides [Discrete Comput. Geom. (2014)]. We also show that, for every set \\(P\\) of \\(n\\) points that lie on a \\(d\\)-dimensional constant-degree algebraic variety \\(V\\) in \\(\\mathbb{R}^D\\), there exists a subset \\(S\\subset P\\) of size at least \\(\\Omega(n^{\\frac{4}{9+12(d-1)}})\\), such that \\(S\\) spans \\(\\binom{|S|}{2}\\) distinct distances. This improves the earlier bound of \\(\\Omega(n^{\\frac{1}{3d}})\\) of Conlon et al. [SIAM J. Discrete Math. (2015)]. Both results are consequences of a common technical tool, given in Lemma 2.7 below.

We characterize when bivariate real analytic functions are \"dimension expanding\" when applied to a Cartesian product. If \\(P\\) is a bivariate real analytic function that is not locally of the form \\(P(x,y) = h(a(x) + b(y))\\), then whenever \\(A\\) and \\(B\\) are Borel subsets of \\(\\mathbb{R}\\) with Hausdorff dimension \\(0<\\alpha<1\\), we have that \\(P(A,B)\\) has Hausdorff dimension at least \\(\\alpha + \\epsilon\\) for some \\(\\epsilon(\\alpha)>0\\) that is independent of \\(P\\). The result is sharp, in the sense that no estimate of this form can hold if \\(P(x,y) = h(a(x) + b(y))\\). We also prove a more technical single-scale version of this result, which is an analogue of the Elekes-Rónyai theorem in the setting of the Katz-Tao discretized ring conjecture. As an application, we show that a discretized non-concentrated set cannot have small nonlinear projection under three distinct analytic projection functions, provided that the corresponding 3-web has non-vanishing Blaschke curvature.