Problem 3. Structure for point-line incidences.
The exact asymptotic bound for point-line incidences in was derived in the early 1980’s. Although several decades have passed, we still know relatively little about the point-line configurations that lead to many incidences. This is the structural problem: characterizing the point-line configurations that achieve the asymptotically maximal number of incidences.
It is not surprising that we do not know much about the structural problem, since this is the case for most problems in this part of discrete geometry – even after the extremal bound is obtained, we are not able say much about the structure of the extremal solutions. The major exception that comes to mind is the Green-Tao structural result for ordinary lines.
Back to point-line incidences in , consider the case of
points and
lines. The Szemerédi–Trotter theorem states that the maximum number of incidences in this case is
. We have two constructions that achieve this bound: The original construction of Erdős and a simplified construction by Elekes. The points of the first construction are a
section of the integer lattice
. The points in the second construction are an
section of
(see figure below). One can further play with these constructions by applying projective transformations and taking subsets of the lattice.
Here are some structural question one might ask about point-line configurations with incidences:
- Are
and
the only lattice sizes that can achieve
incidences? For example, can we use an
section of
? Is there a continuous spectrum of lattice sizes or are there only a few sporadic sizes?
- Must there always be a line that contains
of the points? (not necessarily a line from the set of
lines). It is easy to show that there must exist a line containing
points. I am not aware of any stronger bound for this problem.
- Must we rely on a section of
? (possibly with a projective transformation and removing some points) Are there other lattices that work? Are there constructions that do not come from lattices?