Beck's theorem (geometry)

From Wikipedia, the free encyclopedia

In incidence geometry, Beck's theorem is a more quantitative form of the more classical Sylvester–Gallai theorem. It says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.

Precisely, the theorem asserts the existence of positive constants C, K such that that given any n points in the plane, at least one of the following statements is true:

1. There is a line which contains at least n/C of the points.
2. There exist at least n² / K lines, each of which contains at least two of the points.

In Beck's original argument, C is 100 and K is an unspecified constant; it is not known what the optimal values of C and K are.

[edit] Proof

A proof of Beck's theorem can be given as follows. Consider a set P of n points in the plane. Let j be a positive integer. Let us say that a pair of points A, B in the set P is j-connected if the line connecting A and B contains between 2^j and 2^{j + 1} − 1 points of P (including A and B).

From the Szemerédi–Trotter theorem, the number of such lines is O(n² / 2^3j + n / 2^j), as follows: Consider the set P of n points, and the set L of all those lines spanned by pairs of points of P that contain at least 2^j points of P. Note that , since no two points can lie on two distinct lines. Now using Szemerédi–Trotter theorem, it follows that the number of incidences between P and L is at most O(n² / 2^2j + n). All the lines connecting j-connected points also lie in L, and each contributes at least 2^j incidences. Therefore the total number of such lines is O(n² / 2^3j + n / 2^j).

Since each such line connects together O(2^2j) pairs of points, we thus see that at most O(n² / 2^j + 2^jn) pairs of points can be j-connected.

Now, let C be a large constant. By summing the geometric series, we see that the number of pairs of points which are j-connected for some j satisfying is at most O(n² / C).

On the other hand, the total number of pairs is . Thus if we choose C to be large enough, we can find at least n² / 4 pairs (for instance) which are not j-connected for any . The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n/C points. If the latter case holds for even one of these pairs, then we have the first conclusion of Beck's theorem. Thus we may assume that all of the n² / 4 pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most C(2C − 1) pairs of points. Thus there must be at least n² / 4C(2C − 1) lines connecting at least two points, and the claim follows by taking K = 4C(2C − 1).

[edit] References

1. Jozsef Beck, On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry, Combinatorica 3 (1983), 281--297.