Explore the vast range of titles available.

It is conjectured that if a finite set of points in the plane contains many collinear triples, then part of the set has a structure. We will show that under some combinatorial conditions, such pointsets have special configurations of triples, proving a case of Elekes’ conjecture. Using the techniques applied in the proof, we show a density version of Jamison’s theorem. If the number of distinct directions between many pairs of points of a point set in a convex position is small, then many points are on a conic.

We study arrangements of intervals in R2 for which many pairs are concyclic. We show that any set of intervals with many concyclic pairs must have underlying algebraic and geometric structure. In the most general case, we prove that the endpoints of many intervals belong to a single bicircular quartic curve.

We prove almost tight bounds on the number of incidences between points and k -dimensional varieties of bounded degree in R d . Our main tools are the polynomial ham sandwich theorem and induction on both the dimension and the number of points.

The first open case of the Brown–Erdős–Sós conjecture is equivalent to the following: for every c > 0, there is a threshold n0 such that if a quasigroup has order n ⩾ n0, then for every subset S of triples of the form (a, b, ab) with |S| ⩾ cn2, there is a seven-element subset of the quasigroup which spans at least four triples of S. In this paper we prove the conjecture for finite groups.

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.

We study arrangements of intervals in R2 for which many pairs form trapezoids. We show that any set of intervals forming many trapezoids must have underlying algebraic structure, which we characterise. This leads to some unexpected examples of sets of intervals forming many trapezoids, where an important role is played by degree 2 curves.

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 noncollinear points in the plane, and let P be a set of n other points in the plane. We show that the number of distinct distances between p 1, p 2, p 3 and the points of P is Ω(n 6/11), improving the lower bound Ω(n 0.502) of Elekes and Szabó [4] (and considerably simplifying the analysis).

We describe constructions of infinite graphs which are not representable as integral graphs in the plane, addressing a question of Erdős. We also mention some related problems.

In their seminal paper Erdös and Szemerédi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdös-Szemerédi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.