En geometría de incidencia , el teorema de De Bruijn–Erdős , publicado originalmente por Nicolaas Govert de Bruijn y Paul Erdős en 1948, [1] establece un límite inferior para el número de líneas determinadas por n puntos en un plano proyectivo . Por dualidad , este es también un límite para el número de puntos de intersección determinados por una configuración de líneas. [2]
Aunque la prueba dada por De Bruijn y Erdős es combinatoria , De Bruijn y Erdős notaron 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. [1]
Sea P una configuración de n puntos en un plano proyectivo, no todos sobre una recta. Sea t el número de rectas determinado por P . Entonces,
El teorema es claramente cierto para tres puntos no colineales. Procedemos por inducción .
Supongamos que n > 3 y que el teorema es cierto para n − 1. Sea P un conjunto de n puntos, no todos colineales. El teorema de Sylvester-Gallai establece que existe una línea que contiene exactamente dos puntos de P. Estas dos líneas de puntos se denominan líneas ordinarias . Sean a y b los dos puntos de P en una línea ordinaria.
Si la eliminación del punto a produce un conjunto de puntos colineales, entonces P genera un lápiz casi completo de n líneas (las n - 1 líneas ordinarias que pasan por 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. Por la hipótesis de inducción, P' determina al menos n − 1 rectas. La recta ordinaria determinada por a y b no se encuentra entre ellas, por lo que P determina al menos n rectas.
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 . [3]