Beck's theorem (geometry)
In discrete geometry, Beck's theorem is any of several different results, two of which are given below. Both appeared, alongside several other important theorems, in a well-known paper by József Beck. The two results described below primarily concern lower bounds on the number of lines "determined" by a set of points in the plane. (Any line containing at least two points of point set is said to be "determined" by that point set.) Erdős–Beck theorem. The Erdős–Beck theorem is a variation of a classical result by L. M. Kelly and W. O.  J. Moser involving configurations of "n" points of which at most "n" − "k" are collinear, for some 0 < "k" < "O"(). They showed that if "n" is sufficiently large, relative to "k", then the configuration spans at least "kn" − (1/2)(3"k" + 2)("k" − 1) lines. Elekes and Csaba Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2"n" points in R all lying on two skew lines. Assume that these two lines are each incident to "n" points. Such a configuration of points spans only 2"n  planes. Thus, a trivial extension to the hypothesis for point sets in R is not sufficient to obtain the desired result. This result was first conjectured by Erdős, and proven by Beck. (See Theorem 5.2" in.) Statement. Let "S" be a set of "n" points in the plane. If no more than "n" − "k" points lie on any line for some 0 ≤ "k" < "n" − 2, then there exist Ω("nk") lines determined by the points of "S". Beck's theorem. Beck's theorem 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. Although not mentioned in Beck's paper, this result is implied by the Erdős–Beck theorem. Statement. The theorem asserts the existence of positive constants "C", "K" such that given any "n" points in the plane, at least one of the following statements is true: 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 . 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 formula_2 and formula_3 points of "P" (including "A" and "B"). From the Szemerédi–Trotter theorem, the number of such lines is formula_4, 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 formula_5 points of P". Since no two points can lie on two distinct lines formula_6. Now using Szemerédi–Trotter theorem, it follows that the number of incidences between "P" and "L" is at most formula_7. All the lines connecting "j-connected" points also lie in "L", and each contributes at least formula_2 incidences. Therefore, the total number of such lines is formula_9. Since each such line connects together formula_10 pairs of points, we thus see that at most formula_11 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 formula_12 is at most formula_13. On the other hand, the total number of pairs is formula_14. Thus if we choose "C" to be large enough, we can find at least formula_15 pairs (for instance) which are not "j"-connected for any formula_12. The lines that connect these pairs either pass through fewer than 2"C" 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 formula_17 pairs are connected by lines which pass through fewer than 2"C" points. But each such line can connect at most formula_18 pairs of points. Thus there must be at least formula_19 lines connecting at least two points, and the claim follows by taking formula_20.