Micha Sharir, Tel Aviv University
Sharing joints, in moderation: A groundshaking clash between algebraic
and combinatorial geometry
Abstract
--------
About half a year ago, Larry Guth and Nets Hawk Katz have obtained the
tight upper bound $O(n^{3/2})$ on the number of joints in a set of $n$
lines in 3-space, where a joint is a point incident to at least three
non-coplanar lines, thus closing the lid on a problem that has been
open for nearly 20 years. While this in itself is a significant
development, the groundbreaking nature of their work is the proof
technique, which uses fairly simple tools from algebraic geometry, a
totally new approach to combinatorial problems of this kind in
discrete geometry.
In this talk I will present a simplified version of the new machinery,
and the further results that we have so far obtained, by adapting and
exploiting the algebraic machinery.
The first main new result is: Given a set $L$ of $n$ lines in space, and a
subset of $m$ joints of $L$, the number of incidences between these
joints and the lines of $L$ is $O(m^{1/3}n)$, which is worst-case tight
for $m\ge n$. In fact, this holds for any sets of $m$ points and $n$
lines, provided that each point is incident to at least three lines,
and no plane contains more than $O(n)$ points.
The second set of results is strongly related to the celebrated
problem of Erd{\H o}s on distinct distances in the plane. We reduce
this problem to a problem involving incidences between points and
helices (or parabolas) in 3-space, and formulate some conjectures
concerning the incidence bound. Settling these conjectures in the
affirmative would have almost solved Erd{\H o}s's problem. So far we
have several partial positive related results, which yield, among
other results, that the number of distinct (mutually non-congruent)
triangles determined by $s$ points in the plane is always
$\Omega(s^2/\log s)$, which is almost tight in the worst case, since
the integer lattice yields an upper bound of $O(s^2)$.
Joint work with Haim Kaplan and (the late) Gy\"orgy Elekes