BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The d-dimensional algebraic connectivity ad(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 Rd. Here, we analyze the d-dimensional algebraic connectivity of complete graphs. In particular, we show that, for d≥3, ad(Kd+1)=1, and for n≥2d, ⌈2dn⌉−2d+1≤ad(Kn)≤3(d−1)2n+31.
We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed d≥1, we show that with high probability, the graph becomes rigid in Rd at the very moment its minimum degree becomes d, and it becomes globally rigid in Rd at the very moment its minimum degree becomes d+1.
We show that, for a constant-degree algebraic curve γ in RD, every set of n points on γ spans at least Ω(n4/3) distinct distances, unless γ is an {\it algebraic helix} (see Definition 1.1). This improves the earlier bound Ω(n5/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 RD, there exists a subset S⊂P of size at least Ω(n9+12(d−1)4), such that S spans (2∣S∣) distinct distances. This improves the earlier bound of Ω(n3d1) of Conlon et al. [SIAM J. Discrete Math. (2015)]. Both results are consequences of a common technical tool, given in Lemma 2.7 below.
Let L be a sequence (ℓ1,ℓ2,…,ℓn) of n lines in C3. We define the {\it intersection graph} GL=([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 {\it realization} of G if G⊂GL. 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 {\it generic} realization L of G that consists of n pairwise distinct lines, we have GL=Kn, 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.
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ó [Combin. Probab. Comput., 2009]. The problem is a special instance of a more general problem studied by Elekes and Szabó [Combinatorica, 2012] (and by Elekes and Rónyai [J. Combin. Theory Ser. A, 2000]).
Let F∈C[x,y,s,t] be an irreducible constant-degree polynomial, and let A,B,C,D⊂C be finite sets of size n. We show that F vanishes on at most O(n8/3) points of the Cartesian product A×B×C×D, unless F has a special group-related form. A similar statement holds for A,B,C,D of unequal sizes. This is a four-dimensional extension of our recent improved analysis of the original Elekes-Szabó theorem in three dimensions. We give three applications: an expansion bound for three-variable real polynomials that do not have a special form, a bound on the number of coplanar quadruples on a space curve that is neither planar nor quartic, and a bound on the number of four-point circles on a plane curve that has degree at least five.
A finite set of real numbers is called convex if the differences between consecutive elements form a strictly increasing sequence. We show that, for any pair of convex sets A,B⊂R, each of size n1/2, the convex grid A×B spans at most O(n37/17log2/17n) unit-area triangles. This improves the best known upper bound O(n31/14) recently obtained in \cite{RS}. Our analysis also applies to more general families of sets A, B, known as sets of Szemerédi--Trotter type.
We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n20/9), improving the earlier bound O(n9/4) of Apfelbaum and Sharir [Discrete Comput. Geom., 2010]. 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 Ω(n2), for any triple of lines (it is always O(n2) in this case). (ii) We show that if S is a {\em convex grid} of the form A×B, where A, B are {\em convex} sets of n1/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(n31/14) unit-area triangles.
We consider the RMS distance (sum of squared distances between pairs of points) under translation between two point sets in the plane, in two different setups. In the partial-matching setup, each point in the smaller set is matched to a distinct point in the bigger set. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision of the plane and derive improved bounds on its complexity. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. In the Hausdorff setup, each point is paired to its nearest neighbor in the other set. We develop algorithms for finding a local minimum of the Hausdorff RMS distance in nearly linear time on the line, and in nearly quadratic time in the plane. These improve substantially the worst-case behavior of the popular ICP heuristics for solving this problem.
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 degf), 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 (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 degf, unless f has one of the aforementioned special forms. This result provides a unified tool for improving bounds in various Erd\H os-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 parametric algebraic curve which does not contain a line, in any dimension, is Ω(n4/3), extending the result of Pach and de Zeeuw (2013) and improving the bound of Charalambides (2012), 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 be a set of n points in the plane that determines at most n/5 distinct distances. We show that no line can contain more than O(n43/52polylog(n)) points of P. We also show a similar result for rectangular distances, equivalent to distances in the Minkowski plane, where the distance between a pair of points is the area of the axis-parallel rectangle that they span.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.