The local properties problem of Erd\Hos and Shelah generalizes many Ramsey problems and some distinct distances problems. In this work, we derive a variety of new bounds for the local properties problem and its variants, by extending the color energy technique---a variant of the additive energy technique from additive combinatorics (color energy was originally introduced by the last two authors [C. Pohoata and A. Sheffer, Combinatorica, 39 (2019), pp. 705--714]). We generalize the concept of color energy to higher color energies and combine these with bounds on the extremal numbers of even cycles. Let $f(n,k,\ell)$ denote the minimum number of colors required to color the edges of $K_n$ such that every $k$ vertices span at least $\ell$ colors. It can be easily shown that $f(n,k,\binom{k}{2}-\lfloor \frac{k}{2}\rfloor +2)=\Theta(n^2)$. Erdös and Gyárfás asked what happens when $\ell=\binom{k}{2}-\lfloor k/2\rfloor +1$, one away from the easy case, and derived the bound $f\left(n,k,\ell\right) =\Omega(n^{4/3})$. Our technique significantly improves this to $f(n,k,\binom{k}{2} - \lfloor k/2\rfloor +1) = \Omega(n^{2- 8/k})$.

We introduce the bisector energy of an n-point set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^2). We also prove the lower bound M(n)n^2, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^a points of P, or there exist n^{8/5 - 12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{-2/5}n^{8/5}, M(n)^{-1}n^2}). This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.

We establish an improved upper bound for the number of incidences between m points and n arbitrary circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension ≥ 2, is O*(m2/3n2/3 + m6/11n9/11+m+n) (where the O*() notation hides sub-polynomial factors). Since all the points and circles may lie on a common plane or sphere, it is impossible to improve the bound in R^3 without first improving it in the plane.

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, nonweighted common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits $\Omega (8.65^n)$ different triangulations. This improves the bound $\Omega (8.48^n)$ achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We obtain a new lower bound of $\Omega(12.00^n)$ for the number of noncrossing spanning trees of the double chain composed of two convex chains. The previous bound, $\Omega(10.42^n)$, stood unchanged for more than 10 years. (iii) Using a recent upper bound of $30^n$ for the number of triangulations, due to Sharir and Sheffer, we show that $n$ points in the plane in general position admit at most $O(68.62^n)$ noncrossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest tours can be exponential in $n$ for points in general position. These tours are automatically noncrossing. Likewise, we show that the number of longest noncrossing tours can be exponential in $n$. It was known that the number of shortest noncrossing perfect matchings can be exponential in $n$, and here we show that the number of longest noncrossing perfect matchings can be also exponential in $n$. It was known that the number of longest noncrossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we re-derive tight bounds for the number of longest and shortest tours with some simpler arguments. We also give a combinatorial characterization of longest tours, which yields an $O(n\log n)$ time algorithm for computing them.

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of N points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are O(1.8181N) for cycles and O(1.1067N) for matchings. These imply a new upper bound of O(54.543N) on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound O(68.664N)). Our analysis is based on a weighted variant of Kasteleyn's linear algebra technique.

We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of \(O^*\left(187.53^N \right)\) for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound 207.85 N in Hoffmann et al.[14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwise-crossing edges (more commonly known as k -quasi-planar graphs). For k = 3 and k = 4, we prove that, for any set S of N points in the plane, the number of graphs that have a straight-edge k -quasi-planar embedding over S is only exponential in N . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.

We study the expected number of interior vertices of degree i in a triangulation of a point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N > i and that at least some fixed fraction of the points are interior).