Some geometric problems in need of some additive combinatorics

David Wood
Monash University

I will discuss a number of open problems in combinatorial geometry that seem to need additive combinatorics in their solution.
The recurring theme is the notion of the visibility graph of a point set P, which has vertex set P, where distinct points v and w in P are adjacent whenever the line segment vw contains no other point in P.
Many interesting results and open problems are obtained by studying graph-theoretic properties of visibility graphs. For example, Székely's simple proof of the Szemerédi-Trotter Theorem can be thought of as applying the crossing lemma to a particular subgraph of the visibility graph. And Beck's Theorem can be thought of as saying that visibility graphs have many edges. Open problems related to elliptic curves, Freiman's Theorem and the Hales-Jewett Theorem also arise.


Back to Workshop I: Combinatorial Geometry Problems at the Algebraic Interface