Given a set of points and a set of lines, both in , an incidence is a pair . Answering a question of Erdos and Purdy, Szemeredi and Trotter proved the following important theorem:
The Szemeredi-Trotter theorem is one of the most remarkable results in incidence geometry not only because it is extremely useful in applications all across combinatorics, but also because it is one of the few optimal incidence theorems available. Indeed, there are two somewhat different constructions achieving the equality (up to constants): one due to Elekes and another one, less well-known, due to Erdos himself.
In this blog post, we will discuss an interesting result of Solymosi, which showcases something that these two constructions have in common (and as a matter of fact, something that all configurations with incidences have in common).
Theorem. (Solymosi) Let be a set of points and let be a set of lines, both in . Suppose that
Then, there must exist three non-collinear points in , with the property that every pair of points among them determines a line which is from the set .
From now on, we will also no-so-surprisingly refer to such local configurations simply as triangles, since that’s what they actually are in the plane, however note that this could easily become confusing if one is not careful, since graph theoretically these configurations actually represent copies of a cycle of length six in the incidence graph . Solymosi’s theorem can be therefore rephrased as saying that for every set of points and every set of lines which do not determine any triangles, we have that
We will actually not dwell too much on the proof of Solymosi’s theorem, since in this post I would like to instead focus on a lower bound construction. Nonetheless, I’d like to at least record the strategy, since the idea is very simple and interesting. As a starting point, recall that the Szemeredi-Trotter theorem can be proved in a few ways by amplifying the trivial bounds and . Most famously, this has been done in an absolutely beautiful indirect manner by Szekely via the so-called crossing number inequality; however, more modernly, this has also been achieved in various other more practical ways by using partitioning theorems (such as the Guth-Katz polynomial partitioning theorem but also using older partitioning results such as the simplicial cutting theorem of Matousek (used also by Solymosi); see for instance these lecture notes of Guth or this blog post of Tao). Solymosi’s main observation is that under the additional assumption that the incidence graph contains no copy of a cycle of length six, one can improve on the trivial inequalities above even before the amplification step. More precisely, one can show for instance that as follows.
First, let be the set of points in which lie on at most two lines from ; note that
Then, consider the graph with vertex set and with edges defined as follows: for each point , consider the set of lines which contain of , and cover up the vertices corresponding to in by edge-disjoint triangles (up to a small error). The number of edges in thus constructed is then roughly the same as the number of incidences , so if for some reason , this would mean that has edge-disjoint triangles. By the triangle removal lemma, having this many edge-disjoint triangles would further imply that our graph must actually have triangles in total, and so some of these triangles would most definitely have to come from different points in , by design. It is easy to see that this would immediately be in conflict with the hypothesis that there are no cycles of length six in the incidence graph . Therefore, it follows that , which gives the claim above. Amplfying this bound instead of the trivial bound, one can then recover Solymosi’s theorem.
We will now move on to describe a construction of a set points and a set lines with many incidences and no triangles, which shows that Solymosi’s theorem is in some sense sharp in the regime when or for every . The construction is in the style of Elekes’s construction for the original Szemeredi-Trotter theorem, but with an additive combinatorics twist to force out triangles.
A set of positive integers is called a non-averaging set of order if for each , the equation
has no solutions with , , all in and all pairwise distinct. Furthermore, let denote the size of the largest non-averaging set of order inside the interval . In particular, note that , where the latter denotes as usual the size of the largest three-term progression free set inside . It is well-known that there exists some absolute constant such that for every sufficiently large one has
thanks to a celebrated construction due to Behrend. Interestingly, it is not too hard to modify this construction to show that also contains very large non-averaging sets of order , for every which is reasonably small compared to . Indeed, the following nice observation of Stanchescu holds.
Theorem (Stanchescu). For every , there exists some absolute constant such that
for every sufficiently large .
We can now finally get to the construction. Let and denote some large positive integers, with a precise relationship between them to be specified later. For now, we shall only think of as being much larger than . Let then be a non-averaging set of order inside and satisfying
for some absolute constant . Define the set of points by
Let be the line in defined by the equation , and let be the set of lines defined by
Note that , whereas . Furthermore, note that for every line in and every , there is a unique element in such that lies on . In particular, each line determines at least incidences with , so
In particular, if say for some , then for every , and
We next verify that in this configuration there are no non-collinear three points in , with each pair lying on a line from . We argue this by contradiction. Suppose there are three lines in and three points in such that their vertices induce a cycle of length six in , and the points , , are not collinear. Without loss of generality, suppose the lines and meet at , lines and meet at , and the lines and meet at .
Also, for each , let be described by the equation , and without loss of generality assume that . It is easy to check that by definition of , we have that , and we also have similar equations for and .
Adding up these equations, it follows that
But are all in and recall is a non-averaging set of order , so this would imply that . This is a contradiction, since we assumed that the points , , are not collinear.
It would interesting to see in the future (maybe a future blog post!) whether the triangle removal lemma could be combined instead with the crossing number inequality proof of Szemeredi-Trotter (rather than the cutting method proof) to give an alternate proof for
Another natural question also seems to be whether one can improve quantitatively on the bound above by proving new bounds for the triangle removal lemma which are specific to this geometric setting. This of course may be difficult since the only data point where this type of thing has been accomplished so far is the arithmetic setup in vector spaces over finite fields.