Teorema de De Bruijn–Erdős (geometria de incidência)

Teorema de De Bruijn–Erdős (geometria de incidência) This article is about the number of lines determined by a finite set of points. For coloring infinite graphs, see De Bruijn–Erdős theorem (teoria dos grafos).

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. Por dualidade, 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.

Conteúdo 1 Declaração do teorema 2 Euclidean proof 3 J. H. Conway's proof 4 Referências 5 Sources Statement of the theorem A near-pencil on seven points Let P be a configuration of n points in a projective plane, not all on a line. Let t be the number of lines determined by P. Então, t ≥ n, and if t = n, any two lines have exactly one point of P in common. Nesse caso, P is either a projective plane or P is a near pencil, meaning that exactly n - 1 of the points are collinear. Euclidean 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 there is a line containing exactly two points of P. Such two point lines are called ordinary lines. Let a and b be the two points of P on an ordinary line.

If the removal of point a produces a set of collinear points then P generates a near pencil of n lines (the n - 1 ordinary lines through a plus the one line containing the other n - 1 pontos).

Por outro lado, the removal of a produces a set, P' , of n − 1 points that are not all collinear. Pela hipótese de indução, P' determines at least n − 1 lines. The ordinary line determined by a and b is not among these, so P determines at least n lines.

J. H. Conway's proof John Horton Conway has a purely combinatorial proof which consequently also holds for points and lines over the complex numbers, quaternions and octonions.[1] References ^ Stasys Jukna, Extremal Combinatorics, Second edition, Editora Springer, 2011, Páginas 167 - 168. Sources De Bruijn, N. G.; Floresta, P. (1948), "On a combinatioral [sic] problema" (PDF), Investigações matemáticas, 10: 421-423. Batten, Lynn Margaret (1997), "2.2 The De Bruijn–Erdős theorem", Combinatorics of Finite Geometries (2ª edição), Cambridge University Press, pp. 25-27, ISBN 0-521-59014-0 hide vte Incidence structures Representation Incidence matrixIncidence graph Fields Combinatorics Block designSteiner systemGeometry IncidenceProjective planeGraph theory HypergraphStatistics Blocking Configurations Complete quadrangleFano planeMöbius–Kantor configurationPappus configurationHesse configurationDesargues configurationReye configurationSchläfli double sixCremona–Richmond configurationKummer configurationGrünbaum–Rigby configurationKlein configurationDual Theorems Sylvester–Gallai theoremDe Bruijn–Erdős theoremSzemerédi–Trotter theoremBeck's theoremBruck–Ryser–Chowla theorem Applications Design of experimentsKirkman's schoolgirl problem Categories: Theorems in projective geometryEuclidean plane geometryTheorems in discrete geometryIncidence geometryPaul Erdős