En geometría de incidencia , el teorema de De Bruijn-Erdős , publicado originalmente por Nicolaas Govert de Bruijn y Paul Erdős ( 1948 ), establece un límite inferior en el número de líneas determinadas por n puntos en un plano proyectivo . Por dualidad , esto también es un límite en el número de puntos de intersección determinados por una configuración de líneas.
Aunque la demostración dada por De Bruijn y Erdős es combinatoria , De Bruijn y Erdős señalaron en su artículo que el resultado análogo ( euclidiano ) es una consecuencia del teorema de Sylvester-Gallai , por una inducción sobre el número de puntos.
Declaración del teorema
Sea P una configuración de n puntos en un plano proyectivo, no todos en una línea. Vamos t ser el número de líneas determinadas por P . Luego,
- t ≥ n , y
- si t = n , dos rectas cualesquiera tienen exactamente un punto de P en común. En este caso, P es un plano proyectivo o P es un lápiz cercano , lo que significa que exactamente n - 1 de los puntos son colineales .
Prueba euclidiana
El teorema es claramente cierto para tres puntos no colineales. Procedemos por inducción .
Suponga que n > 3 y el teorema es verdadero para n - 1. Sea P un conjunto de n puntos no todos colineales. El Sylvester-Gallai teorema afirma que hay una línea que contiene exactamente dos puntos de P . Estas dos líneas de puntos se denominan líneas ordinarias . Deje una y b sea los dos puntos de P en una línea de corriente.
Si la eliminación del punto a produce un conjunto de puntos colineales, entonces P genera un lápiz cercano de n líneas (las n - 1 líneas ordinarias a través de a más la línea que contiene los otros n - 1 puntos).
De lo contrario, la eliminación de a produce un conjunto, P ' , de n - 1 puntos que no son todos colineales. Según la hipótesis de inducción, P ' determina al menos n - 1 líneas. La línea ordinaria determinada por una y b no se encuentra entre estos, por lo P determina al menos n líneas.
Prueba de JH Conway
John Horton Conway tiene una prueba puramente combinatoria que, en consecuencia, también es válida para puntos y líneas sobre los números complejos , cuaterniones y octoniones . [1]
Referencias
- ^ Stasys Jukna, Extremal Combinatorics , Segunda edición, Springer Verlag, 2011, páginas 167-168.
Fuentes
- De Bruijn, NG ; Erdős, P. (1948), "On a combinatioral [sic] problem" (PDF) , Indagationes Mathematicae , 10 : 421–423.
- Batten, Lynn Margaret (1997), "2.2 El teorema de De Bruijn-Erdős", Combinatoria de geometrías finitas (2ª ed.), Cambridge University Press, págs. 25-27, ISBN 0-521-59014-0