Beck's theorem (geometry)

Beck's theorem (geometry)

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:

# There is a line which contains at least "n"/C of the points.
# There exist at least n^2/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.

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 / 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 |L| cdot {2^j choose 2} leq {n choose 2}, 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/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/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 / 2^j + 2^j n ) 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 C leq 2^j leq n/C is at most O( n^2 / C).

On the other hand, the total number of pairs is frac{n(n-1)}{2}. Thus if we choose "C" to be large enough, we can find at least n^2 / 4 pairs (for instance) which are not "j"-connected for any C leq 2^j leq n/C. 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^2 / 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^2 / 4C(2C-1) lines connecting at least two points, and the claim follows by taking K = 4C(2C-1).

References

# 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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Beck's theorem — In mathematics, there are two (different) theorems (by two different mathematicians) which go under the name of Beck s theorem.* In category theory, Beck s monadicity theorem (also known as the Beck tripleability theorem), proven by J. M. Beck… …   Wikipedia

  • Beck's monadicity theorem — In category theory, a branch of mathematics, Beck s monadicity theorem asserts that a functor :U: C o Dis monadic if and only if # U has a left adjoint; # U reflects isomorphisms; and # C has coequalizers of U split coequalizer pairs, and U… …   Wikipedia

  • Sylvester–Gallai theorem — The Sylvester–Gallai theorem asserts that given a finite number of points in the Euclidean plane, either all the points are collinear; or there is a line which contains exactly two of the points. This claim was posed as a problem by J. J.… …   Wikipedia

  • Szemerédi–Trotter theorem — In mathematics, the Szemerédi–Trotter theorem is a result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences (i.e. the number of point line pairs, such that the point lies on… …   Wikipedia

  • József Beck — (Budapest, Hungary, February 14, 1952) is a 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… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Discrepancy of hypergraphs — is an area of discrepancy theory. Contents 1 Hypergraph discrepancies in two colors 2 Theorems 2.1 Classic theorems 3 Major open problems …   Wikipedia

  • Théorème de Sylvester–Gallai — Le théorème de Sylvester–Gallai affirme qu étant donné un ensemble fini de points du plan, on a l alternative suivante : soit tous les points sont colinéaires, soit il existe une droite qui contient exactement deux de ces points (droite… …   Wikipédia en Français

  • Monad (category theory) — For the uses of monads in computer software, see monads in functional programming. In category theory, a branch of mathematics, a monad, Kleisli triple, or triple is an (endo )functor, together with two natural transformations. Monads are used in …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”