You are currently browsing the monthly archive for April 2012.
Given an arbitrary set of points in the plane, we would expect most pairs of points to determine distinct lines–this is the “generic” case. The obvious counterexample is when all of the points lie on a single line. Beck’s lemma says that one of these two situations must occur (up to constants) in any finite set of points in the plane.
Beck’s Lemma: Let be a subset of with . Then one of the following holds:
- There is a line containing points of for some constant ,
- or there are distinct lines containing at least two points of each.
Note that (2) is the generic case, while (1) is a counterexample to the generic case.
Proof of Beck’s lemma: We say that are -connected if the line determined by and contains between and points of .
Let be the set of lines determined by containing more than points of . Then by the Szemerédi-Trotter theorem:
If the max is , then we have and if the max is , then we have . Thus
If and are -connected, then they lie on a line of . Thus the number of lines created by a -connected pair is at most . Each such line contains at most pairs of points, so
Let be a positive constant that we will determine later. From now on we focus our attention on such that . For this range of , the number of -connected pairs is bounded above by :
where we bounded the sum of first term by the highest term (i.e. ) and we bounded the second term using the geometric series ().
Since there are pairs of points, if is large enough then there are more than pairs of points that are not -connected for . If one pair is above this range, then the line that they determine contains at least points, which gives us (1). Otherwise we have more than pairs below this region and so we have option (2). QED
Beck’s original proof did not use the Szemeredi-Trotter theorem—in fact, Beck’s paper was published in the same issue of Combinatorica as Szemeredi and Trotter’s paper. Instead he proved the bound on the number of lines containing between and points:
where and . This estimate is sufficient for our argument.