De Bruijn–Erdős theorem (incidence geometry)

De Bruijn–Erdős theorem (incidence geometry)

In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn and Paul Erdős (1948), states a lower bound on the number of lines determined by n points in a projective plane. By duality, this is also a bound on the number of intersection points determined by a configuration of lines.

Although the proof given by De Bruijn and Erdős is combinatorial, De Bruijn and Erdős noted in their paper that the analogous (Euclidean) result is a consequence of the Sylvester–Gallai theorem, by an induction on the number of points.

Statement of the theorem

Let P be a configuration of n points in the projective plane, not all on a line. Let t be the number of lines determined by P. Then,

  • tn,
  • if t = n, any two lines share a point.

Proof

The theorem is clearly true for three non-collinear points. We proceed by induction.

Assume n > 3 and the theorem is true for n − 1. Let P be a set of n points not all collinear. The Sylvester–Gallai theorem states that P determines an ordinary (i.e., two-point) line. Let a and b be two points in P spanned by an ordinary line.

If the removal of point a produces a set of collinear points then the remaining n − 1 > 2 points all lie on a line through b, not incident to a. In which case, remove b to obtain a set, P' , of n − 1 non-collinear points. By our hypothesis, P' spans n − 1 lines which is exactly one fewer than the number of lines spanned by P (since the line connecting a and b is not present).

Otherwise, the removal of a produces a set, P' , of n − 1 non-collinear points. Again, by our hypothesis, P' spans n − 1 lines which is at least one fewer than the number of lines spanned by P.

References


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • De Bruijn–Erdős theorem — See: De Bruijn–Erdős theorem (incidence geometry) De Bruijn–Erdős theorem (graph theory) This disambiguation page lists mathematics articles associated with the same title. If an internal link led …   Wikipedia

  • Nicolaas Govert de Bruijn — Pour les articles homonymes, voir De Bruijn. De Bruijn à Oberwolfach, dans les années 1960 Nicolaas Govert de Bruijn (né le 9 juillet 1918) est un mathématicien …   Wikipédia en Français

  • De Bruijn — is a Dutch surname. It may refer to: Chantal de Bruijn Cornelis de Bruijn, Dutch artist and traveler Daniëlle de Bruijn Inge de Bruijn, Dutch swimmer Nicolaas Govert de Bruijn, Dutch mathematician Maarten de Bruijn Nick de Bruijn Pi de Bruijn In… …   Wikipedia

  • Nicolaas Govert de Bruijn — Born 9 July 1918 (1918 07 09) (age 93) …   Wikipedia

  • де Брёйн, Николас — Николас Говерт де Брёйн Nicolaas Govert de Bruijn …   Википедия

  • Де Брёйн, Николас — Николас Говерт де Брёйн Nicolaas Govert de Bruijn …   Википедия

  • 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

  • Алгоритм Диксона — Алгоритм Диксона  алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и Метод Диксона является обобщением метода Ферма. Содержание 1 …   Википедия

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

Share the article and excerpts

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