En geometría discreta , el teorema de Beck es uno de varios resultados diferentes, dos de los cuales se dan a continuación. Ambos aparecieron, junto con varios otros teoremas importantes, en un artículo bien conocido de József Beck . [1] Los dos resultados descritos a continuación se refieren principalmente a límites inferiores en el número de líneas determinadas por un conjunto de puntos en el plano. (Se dice que cualquier línea que contenga al menos dos puntos de un conjunto de puntos está determinada por ese conjunto de puntos).
El teorema de Erdős-Beck es una variación de un resultado clásico de LM Kelly y WOJ Moser [2] que implica configuraciones de n puntos de los cuales como máximo n − k son colineales, para algún 0 < k < O ( √ n ). Demostraron que si n es suficientemente grande, en relación con k , entonces la configuración abarca al menos kn − (1/2)(3 k + 2)( k − 1) líneas. [3]
Elekes y Csaba Toth observaron que el teorema de Erdős-Beck no se extiende fácilmente a dimensiones superiores. [4] Tomemos como ejemplo un conjunto de 2 n puntos en R 3 que se encuentran todos sobre dos líneas oblicuas . Supongamos que estas dos líneas son incidentes cada una de ellas sobre n puntos. Una configuración de puntos de este tipo abarca solo 2 n planos. Por lo tanto, una extensión trivial de la hipótesis para conjuntos de puntos en R d no es suficiente para obtener el resultado deseado.
Este resultado fue conjeturado por primera vez por Erdős y demostrado por Beck (véase el teorema 5.2 en [1] ) .
Sea S un conjunto de n puntos en el plano. Si no hay más de n − k puntos sobre cualquier recta para algún 0 ≤ k < n − 2, entonces existen Ω( nk ) rectas determinadas por los puntos de S .
El teorema de Beck dice que las colecciones finitas de puntos en el plano caen en uno de dos extremos: uno donde una gran fracción de puntos se encuentran en una sola línea, y otro donde se necesita una gran cantidad de líneas para conectar todos los puntos.
Aunque no se menciona en el artículo de Beck, este resultado está implícito en el teorema de Erdős-Beck . [5]
El teorema afirma la existencia de constantes positivas C , K tales que, dados n puntos en el plano, al menos una de las siguientes afirmaciones es verdadera:
En el argumento original de Beck, C es 100 y K es una constante no especificada; no se sabe cuáles son los valores óptimos de C y K.
Una demostración del teorema de Beck puede darse de la siguiente manera. Considérese un conjunto P de n puntos en el plano. Sea j un entero positivo. Digamos que un par de puntos A , B en el conjunto P es j-conexo si la línea que une A y B contiene entre y puntos de P (incluidos A y B ).
Del teorema de Szemerédi–Trotter , el número de tales líneas es , como sigue: Considérese el conjunto P de n puntos, y el conjunto L de todas aquellas líneas generadas por pares de puntos de P que contienen al menos puntos de P . Como no pueden estar dos puntos en dos líneas distintas . Ahora, utilizando el teorema de Szemerédi–Trotter , se deduce que el número de incidencias entre P y L es como máximo . Todas las líneas que conectan puntos j-conexos también están en L , y cada una contribuye al menos con incidencias. Por lo tanto, el número total de tales líneas es .
Como cada una de estas líneas conecta pares de puntos, vemos que, como máximo, los pares de puntos pueden estar j -conectados.
Ahora, sea C una constante grande. Sumando la serie geométrica , vemos que el número de pares de puntos que están j -conectados para algún j que satisface es como máximo .
Por otra parte, el número total de pares es . Por lo tanto, si elegimos que C sea lo suficientemente grande, podemos encontrar al menos pares (por ejemplo) que no estén j -conectados para ningún . Las líneas que conectan estos pares pasan por menos de 2 C puntos, o pasan por más de n / C puntos. Si el último caso se cumple incluso para uno de estos pares, entonces tenemos la primera conclusión del teorema de Beck. Por lo tanto, podemos suponer que todos los pares están conectados por líneas que pasan por menos de 2 C puntos. Pero cada una de esas líneas puede conectar como máximo pares de puntos. Por lo tanto, debe haber al menos líneas que conecten al menos dos puntos, y la afirmación se sigue tomando .
