A bipartite graph G is semi-algebraic in \mathbb{R}^d if its vertices are represented by point sets P,Q \subset and edges defined as pairs of points (p,q) \in P \times Q that satisfy a Boolean combination fixed number polynomial equations inequalities 2d coordinates. We show for k , the maximum K_{k,k} -free = (P,Q,E) \mathbb{R}^2 with |P| m |Q| n at most O((mn)^{2/3} + n) this bound tight. In dimensions d \geq 3 we all such graphs have C\left((mn)^{ \frac{d}{d+1} \epsilon} n\right) edges,...

We study the maximal number of triangulations that a planar set $n$ points can have, and show it is at most $30^n$. This new bound achieved by careful optimization charging scheme Sharir Welzl (2006), which has led to previous best upper $43^n$ for problem. Moreover, this useful bounding other types (i.e., crossing-free) straight-line graphs on given point set. Specifically, be used derive bounds ($207.84^n$), spanning cycles ($O(68.67^n)$), trees ($O(146.69^n)$), cycle-free ($O(164.17^n)$).

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 plane general position (with no three collinear): perfect matchings, spanning trees, cycles (tours), triangulations. (i) present a bound construction number triangulations set can have. In particular, we show that generalized double chain formed by two almost convex chains admits $\Omega (8.65^n)$ different This improves (8.48^n)$...

We prove that, for every set of $n$ points $\mathcal{P}$ in ${\mathbb R}^2$, a random plane graph drawn on is expected to contain less than $n/10.18$ isolated vertices. In the other direction, we construct point where number vertices about $n/23.32$. For $i\ge 1$, that degree $i$ always $n/\sqrt{\pi i}$. Our analysis based cross-graph charging schemes. That is, move charge between from different graphs same set. This leads information behavior graph.

We completely characterize point-line configurations with $\Theta(n^{4/3})$ incidences when the point set is a section of integer lattice. This can be seen as main special case structural Szemerédi-Trotter problem. also derive partial characterization for several generalizations: (i) rule out concurrent lines Cartesian product an arithmetic progression and arbitrary set. (ii) study where one or both sets are generalized progression. Our proofs rely on deriving properties multiplicative energies.

We establish an improved upper bound for the number of incidences between m points and n circles in three dimensions. The previous best known bound, originally established planar case later extended to any dimension $\ge 2$, is $O*(m^{2/3}n^{2/3} + m^{6/11}n^{9/11}+m+n)$, where $O*(\cdot)$ notation hides sub-polynomial factors. Since all may lie on a common plane (or sphere), it impossible improve R^3 without first improving plane. Nevertheless, we show that if set required be "truly...

We survey the variants of Erdős' distinct distances problem and current best bounds for each those.

NASA's Juno mission provided exquisite measurements of Jupiter's gravity field that together with the Galileo entry probe atmospheric constrains interior structure giant planet. Inferring its range remains a challenging inverse problem requiring computationally intensive search combinations various planetary properties, such as cloud-level temperature, composition, and core features, computation ~10^9 models. We propose an efficient deep neural network (DNN) model to generate high-precision...

We study cross-graph charging schemes for graphs drawn in the plane. These are where charge is moved across vertices of different graphs. Such methods have recently been used to obtain various properties triangulations that embedded a fixed set points generalize this method results other types Specifically, we new bound O *(187.53 N ) (where *(⋅) notation hides polynomial factors) maximum number crossing-free straight-edge can be any specific plane (improving upon previous best upper 207.85...

The local properties problem of Erd\Hos and Shelah generalizes many Ramsey problems some distinct distances problems. In this work, we derive a variety new bounds for the its variants, by extending color energy technique---a variant additive technique from combinatorics (color was originally introduced last two authors [C. Pohoata A. Sheffer, Combinatorica, 39 (2019), pp. 705--714]). We generalize concept to higher energies combine these with on extremal numbers even cycles. Let...

Lower bounds for incidences with hypersurfaces, Discrete Analysis 2016:16, 14pp. A fundamental result in combinatorial geometry, the Szemerédi-Trotter theorem, states that among any $n$ points and $m$ lines $\mathbb R^2$ there can be at most $O((mn)^{2/3}+m+n)$ incidences, where an incidence is a pair consists of one point contained line. Simple examples show this best possible. (The interesting case when are roughly comparable size: terms bound to deal much bigger than or $m$, trivial...

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 N points in plane. More specifically, we bound ratio between (or perfect matchings) a point triangulations it. The respective are O(1.8181N) for O(1.1067N) matchings. These imply new O(54.543N) plane (improving upon previous best O(68.664N)). Our analysis is based weighted variant Kasteleyn's...