En geometría discreta , el teorema de Beck es cualquiera de varios resultados diferentes, dos de los cuales se dan a continuación. Ambos aparecieron, junto con varios otros teoremas importantes, en un conocido artículo de József Beck . [1] Los dos resultados que se describen a continuación se refieren principalmente a los límites inferiores del número de líneas determinadas por un conjunto de puntos en el plano. (Cualquier línea que contenga al menos dos puntos de conjunto de puntos se dice que está determinada por ese conjunto de puntos).
Teorema de Erdős-Beck
El teorema de Erdős-Beck es una variación de un resultado clásico de LM Kelly y WOJ Moser [2] que involucra configuraciones de n puntos de los cuales como máximo n - k son colineales, para algunos 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 señalaron que el teorema de Erdős-Beck no se extiende fácilmente a dimensiones superiores. [4] Tomemos, por ejemplo, un conjunto de 2 n puntos en R 3 que se encuentran todos en dos líneas oblicuas . Suponga que estas dos líneas inciden cada una en n puntos. Tal configuración de puntos abarca solo 2 n planos. Por tanto, una extensión trivial de la hipótesis de conjuntos de puntos en R d no es suficiente para obtener el resultado deseado.
Este resultado fue primero conjeturado por Erdős y probado por Beck. (Ver teorema 5.2 en. [1] )
Declaración
Sea S un conjunto de n puntos en el plano. Si no más de nk puntos se encuentran en cualquier línea para algunos 0 ≤ k < n - 2, entonces existen Ohmio ( nk ) líneas determinadas por los puntos de S .
Prueba
Teorema de beck
El teorema de Beck dice que las colecciones finitas de puntos en el plano caen en uno de dos extremos; uno en el que una gran fracción de puntos se encuentra en una sola línea y otro en el que 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]
Declaración
El teorema afirma la existencia de constantes positivas C , K tales que dados n puntos en el plano, al menos uno de los siguientes enunciados es verdadero:
- Hay una línea que contiene al menos n / C de los puntos.
- Existen al menos líneas, cada una de las cuales contiene al menos dos de los puntos.
En el argumento original de Beck, C es 100 y K es una constante no especificada; no se sabe lo que los valores óptimos de C y K son.
Prueba
Se puede dar una demostración del teorema de Beck de la siguiente manera. Considere un conjunto P de n puntos en el plano. Sea j un número entero positivo. Digamos que un par de puntos A , B en el conjunto P está j-conectado si la línea que conecta A y B contiene entre y puntos de P (incluidos A y B ).
Según el teorema de Szemerédi-Trotter , el número de tales líneas es, de la siguiente manera: Considere el conjunto P de n puntos, y el conjunto L de todas aquellas rectas divididas por pares de puntos de P que contienen al menospuntos de P . Dado que no hay dos puntos que puedan estar en dos líneas distintas. Ahora, usando el teorema de Szemerédi-Trotter , se deduce que el número de incidencias entre P y L es como máximo. Todas las rectas que conectan puntos j conectados también se encuentran en L , y cada una contribuye al menosincidencias. Por lo tanto, el número total de tales líneas es.
Dado que cada una de estas líneas se conecta entre sí pares de puntos, vemos que a lo sumo los pares de puntos se pueden conectar en j .
Ahora, sea C una constante grande. Al sumar 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 otro lado, el número total de pares es . Por lo tanto, si elegimos que C sea lo suficientemente grande, podemos encontrar al menospares (por ejemplo) que no están conectados en j para ningún. Las líneas que conectan estos pares pasan por menos de 2 puntos C o pasan por más de n / C puntos. Si el último caso es válido incluso para uno de estos pares, entonces tenemos la primera conclusión del teorema de Beck. Por tanto, podemos suponer que todos loslos pares están conectados por líneas que pasan por menos de 2 puntos C. Pero cada una de estas líneas puede conectarse como máximopares de puntos. Por lo tanto, debe haber al menos líneas que conectan al menos dos puntos, y la afirmación sigue tomando .
Referencias
- ↑ a b Beck, József (1983). "Sobre la propiedad reticular del plano y algunos problemas de Dirac, Motzkin y Erdős en geometría combinatoria". Combinatorica . 3 : 281-297. doi : 10.1007 / BF02579184 . Señor 0729781 .
- ^ "William OJ Moser" .
- ^ Kelly, LM ; Moser, WOJ (1958), "Sobre el número de líneas ordinarias determinadas por n puntos" , Can. J. Math. , 10 : 210–219, doi : 10.4153 / CJM-1958-024-6
- ^ Elekes, György ; Tóth, Csaba D. (2005). "Incidencias de hiperplanos no demasiado degenerados". Actas del vigésimo primer simposio anual sobre geometría computacional . Pisa, Italia: Simposio anual sobre geometría computacional: 16-21. ISBN 1-58113-991-8.
- ^ El teorema de Beck se puede derivar haciendo k = n (1 - 1 / C ) y aplicando el teorema de Erdős-Beck.