The Taub Faculty of Computer Science Events and Talks

Almost 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 $d$-dimensional space, the maximum number of joints in $L$ (points incident to at least $d$ lines, not all in a common hyperplane) is $\Theta(n^{d/(d-1)})$. The proof is almost ``trivial''.

The second main new result is: Given a set $L$ of $n$ lines in 3-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 third 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 will be presented in the talk.

Joint work with Haim Kaplan, Eugenii Shustin, and (the late) Gy\"orgy Elekes.