Beck's theorem (geometry)
Encyclopedia
In the context of discrete geometry
, Beck's theorem may refer to 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.)
and W.O.J. Moser involving configurations of n points of which at most n−k are collinear, for some 0<k<O(√n). They showed that if n is sufficiently large, relative to k, then the configuration spans at least kn−(1/2)(3k+2)(k−1) lines.
Elekes and Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2n points in R3 all lying on two skew lines
. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd 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.)
Although not mentioned in Beck's paper, this result is implied by the Erdős–Beck theorem.
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.
and 
points of P (including A and B).
From the Szemerédi–Trotter theorem
, the number of such lines is
, 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 
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
. All the lines connecting j-connected points also lie in L, and each contributes at least 
incidences. Therefore the total number of such lines is 
.
Since each such line connects together
pairs of points, we thus see that at most 
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 
.
On the other hand, the total number of pairs is
. Thus if we choose C to be large enough, we can find at least 
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 
pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most 
pairs of points. Thus there must be at least 
lines connecting at least two points, and the claim follows by taking 
.
Discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
, Beck's theorem may refer to 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
József Beck
József Beck is a Harold H. Martin Professor of Mathematics at Rutgers University.His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in discrepancy theory, the algorithmic version of the Lovász local lemma, the two extremes theorem in combinatorial...
. 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. KellyLeroy Milton Kelly
Leroy Milton Kelly was an American mathematician whose research primarily concerned combinatorial geometry.L. M. Kelly received his Ph.D. at the University of Missouri in 1948, advised by Leonard Mascot Blumenthal.-References:...
and W.O.J. Moser involving configurations of n points of which at most n−k are collinear, for some 0<k<O(√n). They showed that if n is sufficiently large, relative to k, then the configuration spans at least kn−(1/2)(3k+2)(k−1) lines.
Elekes and Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2n points in R3 all lying on two skew lines
Skew lines
In solid geometry, skew lines are two lines that do not intersect and are not parallel. Equivalently, they are lines that are not coplanar. A simple example of a pair of skew lines is the pair of lines through opposite edges of a regular tetrahedron...
. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd is not sufficient to obtain the desired result.
This result was first conjectured by Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, and proven by Beck. (See Theorem 5.2 in.)
Statement of the theorem
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 of the theorem
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:- There is a line which contains at least n/C of the points.
- There exist at least
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.
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 and points of P (including A and B).From the Szemerédi–Trotter theorem
Szemerédi–Trotter theorem
The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n...
, the number of such lines is
, 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 points of P. Note that , since no two points can lie on two distinct lines. Now using Szemerédi–Trotter theoremSzemerédi–Trotter theorem
The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n...
, it follows that the number of incidences between P and L is at most
. All the lines connecting j-connected points also lie in L, and each contributes at least incidences. Therefore the total number of such lines is .Since each such line connects together
pairs of points, we thus see that at most 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 .On the other hand, the total number of pairs is
. Thus if we choose C to be large enough, we can find at least 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 pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most pairs of points. Thus there must be at least lines connecting at least two points, and the claim follows by taking .